OpenRaiser/Intern-Atlas huggingface dataset:
Sparse Allreduce: Efficient Scalable Communication for Power-Law Data
Venue: arXiv cs.DC 2013
Year: 2013

Many large datasets exhibit power-law statistics: The web graph, social networks, text data, click through data etc. Their adjacency graphs are termed natural graphs, and are known to be difficult to partition. As a consequence most distributed algorithms on these graphs are communication intensive. Many algorithms on natural graphs involve an Allreduce: a sum or average of partitioned data which is then shared back to the cluster nodes. Examples include PageRank, spectral partitioning, and many machine learning algorithms including regression, factor (topic) models, and clustering. In this paper we describe an efficient and scalable Allreduce primitive for power-law data. We point out scaling problems with existing butterfly and round-robin networks for Sparse Allreduce, and show that a hybrid approach improves on both. Furthermore, we show that Sparse Allreduce stages should be nested instead of cascaded (as in the dense case). And that the optimum throughput Allreduce network should be a butterfly of heterogeneous degree where degree decreases with depth into the network. Finally, a simple replication scheme is introduced to deal with node failures. We present experiments showing significant improvements over existing systems such as PowerGraph and Hadoop.
Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs
Venue: arXiv cs.DS 2013
Year: 2013

We present an approximation scheme for minimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Sparsest Cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time $n^{O(r/ε^2)}$ with approximation ratio $\frac{1+ε}{\min\{1,λ_r\}}$, where $λ_r$ is the $r$'th smallest eigenvalue of the normalized graph Laplacian $\mathcal{L}$. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply $(1+O(ε))$ factor approximation in time $n^{O(r^\ast/ε^2)}$ where is the number of eigenvalues of $\mathcal{L}$ smaller than $1-ε$ (for variants of sparsest cut, $λ_{r^\ast} \ge \mathrm{OPT}/ε$ also suffices, and as $\mathrm{OPT}$ is usually $o(1)$ on interesting instances of these problems, this requirement on $r^\ast$ is typically weaker). For Unique Games, we give a factor $(1+\frac{2+ε}{λ_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/ε)}$ time, improving upon an earlier bound for solving Unique Games on expanders. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$.
Blind Turing-Machines: Arbitrary Private Computations from Group Homomorphic Encryption
Venue: arXiv cs.CR 2013
Year: 2013

Secure function evaluation (SFE) is the process of computing a function (or running an algorithm) on some data, while keeping the input, output and intermediate results hidden from the environment in which the function is evaluated. This can be done using fully homomorphic encryption, Yao's garbled circuits or secure multiparty computation. Applications are manifold, most prominently the outsourcing of computations to cloud service providers, where data is to be manipulated and processed in full confidentiality. Today, one of the most intensively studied solutions to SFE is fully homomorphic encryption (FHE). Ever since the first such systems have been discovered in 2009, and despite much progress, FHE still remains inefficient and difficult to implement practically. Similar concerns apply to garbled circuits and (generic) multiparty computation protocols. In this work, we introduce the concept of a blind Turing-machine, which uses simple homomorphic encryption (an extension of ElGamal encryption) to process ciphertexts in the way as standard Turing-machines do, thus achieving computability of any function in total privacy. Remarkably, this shows that fully homomorphic encryption is indeed an overly strong primitive to do SFE, as group homomorphic encryption with equality check is already sufficient. Moreover, the technique is easy to implement and perhaps opens the door to efficient private computations on nowadays computing machinery, requiring only simple changes to well-established computer architectures.
A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations
Venue: arXiv cs.CG 2013
Year: 2013

Let $P\subset\mathbb{R}^{2}$ be a set of $n$ points. In this paper we show two new algorithms, one to compute the number of triangulations of $P$, and one to compute the number of pseudo-triangulations of $P$. We show that our algorithms run in time $O^{*}(t(P))$ and $O^{*}(pt(P))$ respectively, where $t(P)$ and $pt(P)$ are the largest number of triangulation paths (T-paths) and pseudo-triangulations paths (PT-paths), respectively, that the algorithms encounter during their execution. Moreover, we show that $t(P) = O^{*}(9^{n})$, which is the first non-trivial bound on $t(P)$ to be known. While there already are algorithms that count triangulations in $O^{*}\left(2^n\right)$, and $O^{*}\left(3.1414^{n}\right)$, there are sets of points where the number of T-paths is $O(2^{n})$. In such cases the algorithm herein presented could potentially be faster. Furthermore, it is not clear whether the already-known algorithms can be modified to count pseudo-triangulations so that their running times remain $O^{*}(c^n)$, for some small constant $c\in\mathbb{R}$. Therefore, for counting pseudo-triangulations (and possibly other similar structures) our approach seems better.
On the Complexity of Mining Itemsets from the Crowd Using Taxonomies
Venue: arXiv cs.DB 2013
Year: 2013

We study the problem of frequent itemset mining in domains where data is not recorded in a conventional database but only exists in human knowledge. We provide examples of such scenarios, and present a crowdsourcing model for them. The model uses the crowd as an oracle to find out whether an itemset is frequent or not, and relies on a known taxonomy of the item domain to guide the search for frequent itemsets. In the spirit of data mining with oracles, we analyze the complexity of this problem in terms of (i) crowd complexity, that measures the number of crowd questions required to identify the frequent itemsets; and (ii) computational complexity, that measures the computational effort required to choose the questions. We provide lower and upper complexity bounds in terms of the size and structure of the input taxonomy, as well as the size of a concise description of the output itemsets. We also provide constructive algorithms that achieve the upper bounds, and consider more efficient variants for practical situations.
Towards The Development of a Bishnupriya Manipuri Corpus
Venue: arXiv cs.CL 2013
Year: 2013

For any deep computational processing of language we need evidences, and one such set of evidences is corpus. This paper describes the development of a text-based corpus for the Bishnupriya Manipuri language. A Corpus is considered as a building block for any language processing tasks. Due to the lack of awareness like other Indian languages, it is also studied less frequently. As a result the language still lacks a good corpus and basic language processing tools. As per our knowledge this is the first effort to develop a corpus for Bishnupriya Manipuri language.
Implicit Sensitive Text Summarization based on Data Conveyed by Connectives
Venue: arXiv cs.CL 2013
Year: 2013

So far and trying to reach human capabilities, research in automatic summarization has been based on hypothesis that are both enabling and limiting. Some of these limitations are: how to take into account and reflect (in the generated summary) the implicit information conveyed in the text, the author intention, the reader intention, the context influence, the general world knowledge. Thus, if we want machines to mimic human abilities, then they will need access to this same large variety of knowledge. The implicit is affecting the orientation and the argumentation of the text and consequently its summary. Most of Text Summarizers (TS) are processing as compressing the initial data and they necessarily suffer from information loss. TS are focusing on features of the text only, not on what the author intended or why the reader is reading the text. In this paper, we address this problem and we present a system focusing on acquiring knowledge that is implicit. We principally spotlight the implicit information conveyed by the argumentative connectives such as: but, even, yet and their effect on the summary.
Misfortunes of a mathematicians' trio using Computer Algebra Systems: Can we trust?
Venue: arXiv cs.SC 2013
Year: 2013

Computer algebra systems are a great help for mathematical research but sometimes unexpected errors in the software can also badly affect it. As an example, we show how we have detected an error of Mathematica computing determinants of matrices of integer numbers: not only it computes the determinants wrongly, but also it produces different results if one evaluates the same determinant twice.
On resources and tasks
Venue: arXiv cs.LO 2013
Year: 2013

Essentially being an extended abstract of the author's 1998 PhD thesis, this paper introduces an extension of the language of linear logic with a semantics which treats sentences as tasks rather than true/false statements. A resource is understood as an agent capable of accomplishing the task expressed by such a sentence. It is argued that the corresponding logic can be used as a planning logic, whose advantage over the traditional comprehensive planning logics is that it avoids the representationalframe problem and significantly alleviates the inferential frame problem.
Navigating the massive world of reddit: Using backbone networks to map user interests in social media
Venue: arXiv cs.SI 2013
Year: 2013

In the massive online worlds of social media, users frequently rely on organizing themselves around specific topics of interest to find and engage with like-minded people. However, navigating these massive worlds and finding topics of specific interest often proves difficult because the worlds are mostly organized haphazardly, leaving users to find relevant interests by word of mouth or using a basic search feature. Here, we report on a method using the backbone of a network to create a map of the primary topics of interest in any social network. To demonstrate the method, we build an interest map for the social news web site reddit and show how such a map could be used to navigate a social media world. Moreover, we analyze the network properties of the reddit social network and find that it has a scale-free, small-world, and modular community structure, much like other online social networks such as Facebook and Twitter. We suggest that the integration of interest maps into popular social media platforms will assist users in organizing themselves into more specific interest groups, which will help alleviate the overcrowding effect often observed in large online communities.
The Determinacy of Context-Free Games
Venue: arXiv cs.LO 2013
Year: 2013

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B)).
Call Me MayBe: Understanding Nature and Risks of Sharing Mobile Numbers on Online Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

There is a great concern about the potential for people to leak private information on OSNs, but few quantitative studies on this. This research explores the activity of sharing mobile numbers on OSNs, via public profiles and posts. We attempt to understand the characteristics and risks of mobile numbers sharing behaviour on OSNs and focus on Indian mobile numbers. We collected 76,347 unique mobile numbers posted by 85905 users on Twitter and Facebook and analysed 2997 numbers, prefixed with +91. We observed, most users shared their own mobile numbers to spread urgent information; and to market products and escort business. Fewer female users shared mobile numbers on OSNs. Users utilized other OSN platforms and third party applications like Twitterfeed, to post mobile numbers on multiple OSNs. In contrast to the user's perception of numbers spreading quickly on OSN, we observed that except for emergency, most numbers did not diffuse deep. To assess risks associated with mobile numbers exposed on OSNs, we used numbers to gain sensitive information about their owners (e.g. name, Voter ID) by collating publicly available data from OSNs, Truecaller, OCEAN. On using the numbers on WhatApp, we obtained a myriad of sensitive details (relationship status, BBM pins) of the number owner. We communicated the observed risks to the owners by calling. Few users were surprised to know about the online presence of their number, while a few others intentionally posted it online for business purposes. We observed, 38.3% of users who were unaware of the online presence of their number have posted their number themselves on the social network. With these observations, we highlight that there is a need to monitor leakage of mobile numbers via profile and public posts. To the best of our knowledge, this is the first exploratory study to critically investigate the exposure of Indian mobile numbers on OSNs.
Some results of domination and total domination in the direct product of two fuzzy graphs
Venue: arXiv cs.DM 2013
Year: 2013

In this article we give a new definition of direct product of two arbitrary fuzzy graphs. We define the concepts of domination and total domination in this new product graph. We obtain an upper bound for the total domination number of the product fuzzy graph. Further we define the concept of total alpha-domination number and derive a lower bound for the total domination number of the product fuzzy graph in terms of the total alpha-domination number of the component graphs. A lower bound for the domination number of the same has also been found.
The utilization of social networking as promotion media (Case study: Handicraft business in Palembang)
Venue: arXiv cs.SI 2013
Year: 2013

Nowadays social media (Twitter, Facebook, etc.), not only simply as communication media, but also for promotion. Social networking media offers many business benefits for companies and organizations. Research purposes is to determine the model of social network media utilization as a promotional media for handicraft business in Palembang city. Qualitative and quantitative research design are used to know how handicraft business in Palembang city utilizing social media networking as a promotional media. The research results show 35% craft businesses already utilizing social media as a promotional media. The social media used are blog development 15%, facebook 46%, and twitter etc. are 39%. The reasons they use social media such as, 1) minimal cost, 2) easily recognizable, 3) global distribution areas. Social media emphasis on direct engagement with customers better. So that the marketing method could be more personal through direct communication with customers.
Universal neural field computation
Venue: arXiv cs.FL 2013
Year: 2013

Turing machines and Gödel numbers are important pillars of the theory of computation. Thus, any computational architecture needs to show how it could relate to Turing machines and how stable implementations of Turing computation are possible. In this chapter, we implement universal Turing computation in a neural field environment. To this end, we employ the canonical symbologram representation of a Turing machine obtained from a Gödel encoding of its symbolic repertoire and generalized shifts. The resulting nonlinear dynamical automaton (NDA) is a piecewise affine-linear map acting on the unit square that is partitioned into rectangular domains. Instead of looking at point dynamics in phase space, we then consider functional dynamics of probability distributions functions (p.d.f.s) over phase space. This is generally described by a Frobenius-Perron integral transformation that can be regarded as a neural field equation over the unit square as feature space of a dynamic field theory (DFT). Solving the Frobenius-Perron equation yields that uniform p.d.f.s with rectangular support are mapped onto uniform p.d.f.s with rectangular support, again. We call the resulting representation \emph{dynamic field automaton}.
Designing a brown planthoppers surveillance network based on wireless sensor network approach
Venue: arXiv cs.NI 2013
Year: 2013

This paper proposes a new approach for monitoring brown planthoppers (BPH) swarms using a surveillance network at provincial scale. The topology of this network is identified to a wireless sensor network (WSN), where each node is a real light trap and each edge describes the influence between two nodes, allowing gathering BPH information. Different communication ranges are evaluated to choose a suitable network. The experiments are performed on the light traps surveillance network of Hau Giang province, a typical rice province in the Mekong Delta region of Vietnam.
ARIANNA: pAth Recognition for Indoor Assisted NavigatioN with Augmented perception
Venue: arXiv cs.CV 2013
Year: 2013

ARIANNA stands for pAth Recognition for Indoor Assisted Navigation with Augmented perception. It is a flexible and low cost navigation system for vi- sually impaired people. Arianna permits to navigate colored paths painted or sticked on the floor revealing their directions through vibrational feedback on commercial smartphones.
Analytical Observations on Knapsack Cipher 0/255
Venue: arXiv cs.CR 2013
Year: 2013

We observed few important facts that concerns with the new proposal of knapsack cipher 0/255, recently published by Pham [1]. The author claimed that the time complexity for solving new improved trapdoor knapsack is O(256^N). In this paper, we show that the knapsack cipher 0/255 can be solved in the same time that is required for solving the basic knapsack-cipher proposed by Merkle and Hellman [2]. In other words we claim that the improved version proposed by Pham [1] is technically same as the basic Merkle and Hellman Knapsack-based cryptosystem.
Identification de rôles communautaires dans des réseaux orientés appliquée à Twitter
Venue: arXiv cs.SI 2013
Year: 2013

The notion of community structure is particularly useful when analyzing complex networks, because it provides an intermediate level, compared to the more classic global (whole network) and local (node neighborhood) approaches. The concept of community role of a node was derived from this base, in order to describe the position of a node in a network depending on its connectivity at the community level. However, the existing approaches are restricted to undirected networks, use topological measures which do not consider all aspects of community-related connectivity, and their role identification methods are not generalizable to all networks. We tackle these limitations by generalizing and extending the measures, and using an unsupervised approach to determine the roles. We then illustrate the applicability of our method by analyzing a Twitter network.We show how our modifications allow discovering the fact some particular users called social capitalists occupy very specific roles in this system. --- La notion de structure de communautés est particulièrement utile pour étudier les réseaux complexes, car elle amène un niveau d'analyse intermédiaire, par opposition aux plus classiques niveaux local (voisinage des noeuds) et global (réseau entier). Le concept de rôle communautaire permet de décrire le positionnement d'un noeud en fonction de sa connectivité communautaire. Cependant, les approches existantes sont restreintes aux réseaux non-orientés, utilisent des mesures topologiques ne considérant pas tous les aspects de la connectivité communautaire, et des méthodes d'identification des rôles non-généralisables à tous les réseaux. Nous proposons de résoudre ces problèmes en généralisant les mesures existantes, et en utilisant une méthode non-supervisée pour déterminer les rôles. Nous illustrons l'intérêt de notre méthode en l'appliquant au réseau de Twitter. Nous montrons que nos modifications mettent en évidence les rôles spécifiques d'utilisateurs particuliers du réseau, nommés capitalistes sociaux.
Balancing bike sharing systems (BBSS): instance generation from the CitiBike NYC data
Venue: arXiv cs.AI 2013
Year: 2013

Bike sharing systems are a very popular means to provide bikes to citizens in a simple and cheap way. The idea is to install bike stations at various points in the city, from which a registered user can easily loan a bike by removing it from a specialized rack. After the ride, the user may return the bike at any station (if there is a free rack). Services of this kind are mainly public or semi-public, often aimed at increasing the attractiveness of non-motorized means of transportation, and are usually free, or almost free, of charge for the users. Depending on their location, bike stations have specific patterns regarding when they are empty or full. For instance, in cities where most jobs are located near the city centre, the commuters cause certain peaks in the morning: the central bike stations are filled, while the stations in the outskirts are emptied. Furthermore, stations located on top of a hill are more likely to be empty, since users are less keen on cycling uphill to return the bike, and often leave their bike at a more reachable station. These issues result in substantial user dissatisfaction which may eventually cause the users to abandon the service. This is why nowadays most bike sharing system providers take measures to rebalance them. Over the last few years, balancing bike sharing systems (BBSS) has become increasingly studied in optimization. As such, generating meaningful instance to serve as a benchmark for the proposed approaches is an important task. In this technical report we describe the procedure we used to generate BBSS problem instances from data of the CitiBike NYC bike sharing system.