OpenRaiser/Intern-Atlas huggingface dataset:
Communication Patterns in Mean Field Models for Wireless Sensor Networks
Venue: arXiv cs.PF 2015
Year: 2015

Wireless sensor networks are usually composed of a large number of nodes, and with the increasing processing power and power consumption efficiency they are expected to run more complex protocols in the future. These pose problems in the field of verification and performance evaluation of wireless networks. In this paper, we tailor the mean-field theory as a modeling technique to analyze their behavior. We apply this method to the slotted ALOHA protocol, and establish results on the long term trends of the protocol within a very large network, specially regarding the stability of ALOHA-type protocols.
A Review of Popular Applications on Google Play - Do They Cater to Visually Impaired Users?
Venue: arXiv cs.HC 2015
Year: 2015

The number of applications on online mobile application stores is increasing at a rapid rate. Smart-phones are used by a wide range of people varying in age, and also in the ability to use a smart phone. With the increasing dependency on smart-phones, the paper aims to determine whether the popular applications on Google Play, the official store for Android applications, can be used by people with vision impairment. The accessibility of the applications was tested using an external keyboard, and TalkBack, an accessibility tool developed by Google. It was found that several popular applications on the store were not designed keeping accessibility in mind. It was observed that there exists a weak positive relationship between the popularity of the application and its accessibility. A framework is proposed that can be used by developers to improve the accessibility of an application. The paper also discusses the programming aspects to be considered while developing an Android application, so that the application can be used by sighted as well as visually impaired users.
NeuCoin: the First Secure, Cost-efficient and Decentralized Cryptocurrency
Venue: arXiv cs.CR 2015
Year: 2015

NeuCoin is a decentralized peer-to-peer cryptocurrency derived from Sunny King's Peercoin, which itself was derived from Satoshi Nakamoto's Bitcoin. As with Peercoin, proof-of-stake replaces proof-of-work as NeuCoin's security model, effectively replacing the operating costs of Bitcoin miners (electricity, computers) with the capital costs of holding the currency. Proof-of-stake also avoids proof-of-work's inherent tendency towards centralization resulting from competition for coinbase rewards among miners based on lowest cost electricity and hash power. NeuCoin increases security relative to Peercoin and other existing proof-of-stake currencies in numerous ways, including: (1) incentivizing nodes to continuously stake coins over time through substantially higher mining rewards and lower minimum stake age; (2) abandoning the use of coin age in the mining formula; (3) causing the stake modifier parameter to change over time for each stake; and (4) utilizing a client that punishes nodes that attempt to mine on multiple branches with duplicate stakes. This paper demonstrates how NeuCoin's proof-of-stake implementation addresses all commonly raised "nothing at stake" objections to generic proof-of-stake systems. It also reviews many of the flaws of proof-of-work designs to highlight the potential for an alternate cryptocurrency that solves these flaws.
Generalized K-fan Multimodal Deep Model with Shared Representations
Venue: arXiv cs.LG 2015
Year: 2015

Multimodal learning with deep Boltzmann machines (DBMs) is an generative approach to fuse multimodal inputs, and can learn the shared representation via Contrastive Divergence (CD) for classification and information retrieval tasks. However, it is a 2-fan DBM model, and cannot effectively handle multiple prediction tasks. Moreover, this model cannot recover the hidden representations well by sampling from the conditional distribution when more than one modalities are missing. In this paper, we propose a K-fan deep structure model, which can handle the multi-input and muti-output learning problems effectively. In particular, the deep structure has K-branch for different inputs where each branch can be composed of a multi-layer deep model, and a shared representation is learned in an discriminative manner to tackle multimodal tasks. Given the deep structure, we propose two objective functions to handle two multi-input and multi-output tasks: joint visual restoration and labeling, and the multi-view multi-calss object recognition tasks. To estimate the model parameters, we initialize the deep model parameters with CD to maximize the joint distribution, and then we use backpropagation to update the model according to specific objective function. The experimental results demonstrate that the model can effectively leverages multi-source information and predict multiple tasks well over competitive baselines.
Breaking the News: First Impressions Matter on Online News
Venue: arXiv cs.CY 2015
Year: 2015

A growing number of people are changing the way they consume news, replacing the traditional physical newspapers and magazines by their virtual online versions or/and weblogs. The interactivity and immediacy present in online news are changing the way news are being produced and exposed by media corporations. News websites have to create effective strategies to catch people's attention and attract their clicks. In this paper we investigate possible strategies used by online news corporations in the design of their news headlines. We analyze the content of 69,907 headlines produced by four major global media corporations during a minimum of eight consecutive months in 2014. In order to discover strategies that could be used to attract clicks, we extracted features from the text of the news headlines related to the sentiment polarity of the headline. We discovered that the sentiment of the headline is strongly related to the popularity of the news and also with the dynamics of the posted comments on that particular news.
On Limits of Dense Packing of Equal Spheres in a Cube
Venue: arXiv cs.CG 2015
Year: 2015

We examine packing of $n$ congruent spheres in a cube when $n$ is close but less than the number of spheres in a regular cubic close-packed (ccp) arrangement of $\lceil p^{3}/2\rceil$ spheres. For this family of packings, the previous best-known arrangements were usually derived from a ccp by omission of a certain number of spheres without changing the initial structure. In this paper, we show that better arrangements exist for all $n\leq\lceil p^{3}/2\rceil-2$. We introduce an optimization method to reveal improvements of these packings, and present many new improvements for $n\leq4629$.
Competitive Distribution Estimation
Venue: arXiv cs.IT 2015
Year: 2015

Estimating an unknown distribution from its samples is a fundamental problem in statistics. The common, min-max, formulation of this goal considers the performance of the best estimator over all distributions in a class. It shows that with $n$ samples, distributions over $k$ symbols can be learned to a KL divergence that decreases to zero with the sample size $n$, but grows unboundedly with the alphabet size $k$. Min-max performance can be viewed as regret relative to an oracle that knows the underlying distribution. We consider two natural and modest limits on the oracle's power. One where it knows the underlying distribution only up to symbol permutations, and the other where it knows the exact distribution but is restricted to use natural estimators that assign the same probability to symbols that appeared equally many times in the sample. We show that in both cases the competitive regret reduces to $\min(k/n,\tilde{\mathcal{O}}(1/\sqrt n))$, a quantity upper bounded uniformly for every alphabet size. This shows that distributions can be estimated nearly as well as when they are essentially known in advance, and nearly as well as when they are completely known in advance but need to be estimated via a natural estimator. We also provide an estimator that runs in linear time and incurs competitive regret of $\tilde{\mathcal{O}}(\min(k/n,1/\sqrt n))$, and show that for natural estimators this competitive regret is inevitable. We also demonstrate the effectiveness of competitive estimators using simulations.
A Polynomial Chaos Framework for Designing Linear Parameter Varying Control Systems
Venue: arXiv cs.SY 2015
Year: 2015

Here we use polynomial chaos framework to design controllers for linear parameter varying (LPV) dynamical systems. We assume the scheduling variable to be random and use polynomial chaos approach to synthesize the controller for the resulting linear stochastic dynamical system. The stability of the LPV system is formulated as an exponential mean-square (EMS) stability problem. Two algorithms are presented that guarantee EMS stability of the stochastic system and correspond to parameter dependent and independent Lyapunov functions, respectively. LPV controllers from the polynomial chaos based framework is shown to outperform LPV controller from classical design for an example nonlinear system.
Bayesian Cross Validation and WAIC for Predictive Prior Design in Regular Asymptotic Theory
Venue: arXiv cs.LG 2015
Year: 2015

Prior design is one of the most important problems in both statistics and machine learning. The cross validation (CV) and the widely applicable information criterion (WAIC) are predictive measures of the Bayesian estimation, however, it has been difficult to apply them to find the optimal prior because their mathematical properties in prior evaluation have been unknown and the region of the hyperparameters is too wide to be examined. In this paper, we derive a new formula by which the theoretical relation among CV, WAIC, and the generalization loss is clarified and the optimal hyperparameter can be directly found. By the formula, three facts are clarified about predictive prior design. Firstly, CV and WAIC have the same second order asymptotic expansion, hence they are asymptotically equivalent to each other as the optimizer of the hyperparameter. Secondly, the hyperparameter which minimizes CV or WAIC makes the average generalization loss to be minimized asymptotically but does not the random generalization loss. And lastly, by using the mathematical relation between priors, the variances of the optimized hyperparameters by CV and WAIC are made smaller with small computational costs. Also we show that the optimized hyperparameter by DIC or the marginal likelihood does not minimize the average or random generalization loss in general.
Parameterized Complexity of Asynchronous Border Minimization
Venue: arXiv cs.DS 2015
Year: 2015

Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). In this paper we investigate the parameterized complexity of natural variants of BMP and P-BMP under several natural parameters. We show that BMP and P-BMP are in FPT under the following two combinations of parameters: 1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (l) and the number of rows of the microarray (r); and, 2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMP is in FPT when parameterized by c and l. We complement our tractability results with corresponding hardness results.
Normalization of Non-Standard Words in Croatian Texts
Venue: arXiv cs.CL 2015
Year: 2015

This paper presents text normalization which is an integral part of any text-to-speech synthesis system. Text normalization is a set of methods with a task to write non-standard words, like numbers, dates, times, abbreviations, acronyms and the most common symbols, in their full expanded form are presented. The whole taxonomy for classification of non-standard words in Croatian language together with rule-based normalization methods combined with a lookup dictionary are proposed. Achieved token rate for normalization of Croatian texts is 95%, where 80% of expanded words are in correct morphological form.
Implementing an intelligent version of the classical sliding-puzzle game for unix terminals using Golang's concurrency primitives
Venue: arXiv cs.AI 2015
Year: 2015

An intelligent version of the sliding-puzzle game is developed using the new Go programming language, which uses a concurrent version of the A* Informed Search Algorithm to power solver-bot that runs in the background. The game runs in computer system's terminals. Mainly, it was developed for UNIX-type systems but it works pretty well in nearly all the operating systems because of cross-platform compatibility of the programming language used. The game uses language's concurrency primitives to simplify most of the hefty parts of the game. A real-time notification delivery architecture is developed using language's built-in concurrency support, which performs similar to event based context aware invocations like we see on the web platform.
Bearing-Based Distributed Control and Estimation of Multi-Agent Systems
Venue: arXiv cs.SY 2015
Year: 2015

This paper studies the distributed control and estimation of multi-agent systems based on bearing information. In particular, we consider two problems: (i) the distributed control of bearing-constrained formations using relative position measurements and (ii) the distributed localization of sensor networks using bearing measurements. Both of the two problems are considered in arbitrary dimensional spaces. The analyses of the two problems rely on the recently developed bearing rigidity theory. We show that the two problems have the same mathematical formulation and can be solved by identical protocols. The proposed controller and estimator can globally solve the two problems without ambiguity. The results are supported with illustrative simulations.
Towards Exascale Scientific Metadata Management
Venue: arXiv cs.DB 2015
Year: 2015

Advances in technology and computing hardware are enabling scientists from all areas of science to produce massive amounts of data using large-scale simulations or observational facilities. In this era of data deluge, effective coordination between the data production and the analysis phases hinges on the availability of metadata that describe the scientific datasets. Existing workflow engines have been capturing a limited form of metadata to provide provenance information about the identity and lineage of the data. However, much of the data produced by simulations, experiments, and analyses still need to be annotated manually in an ad hoc manner by domain scientists. Systematic and transparent acquisition of rich metadata becomes a crucial prerequisite to sustain and accelerate the pace of scientific innovation. Yet, ubiquitous and domain-agnostic metadata management infrastructure that can meet the demands of extreme-scale science is notable by its absence. To address this gap in scientific data management research and practice, we present our vision for an integrated approach that (1) automatically captures and manipulates information-rich metadata while the data is being produced or analyzed and (2) stores metadata within each dataset to permeate metadata-oblivious processes and to query metadata through established and standardized data access interfaces. We motivate the need for the proposed integrated approach using applications from plasma physics, climate modeling and neuroscience, and then discuss research challenges and possible solutions.
Dual pivot Quicksort
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we analyse the dual pivot Quicksort, a variant of the standard Quicksort algorithm, in which two pivots are used for the partitioning of the array. We are solving recurrences of the expected number of key comparisons and exchanges performed by the algorithm, obtaining the exact and asymptotic total average values contributing to its time complexity. Further, we compute the average number of partitioning stages and the variance of the number of key comparisons. In terms of mean values, dual pivot Quicksort does not appear to be faster than ordinary algorithm.
Hiding Symbols and Functions: New Metrics and Constructions for Information-Theoretic Security
Venue: arXiv cs.IT 2015
Year: 2015

We present information-theoretic definitions and results for analyzing symmetric-key encryption schemes beyond the perfect secrecy regime, i.e. when perfect secrecy is not attained. We adopt two lines of analysis, one based on lossless source coding, and another akin to rate-distortion theory. We start by presenting a new information-theoretic metric for security, called symbol secrecy, and derive associated fundamental bounds. We then introduce list-source codes (LSCs), which are a general framework for mapping a key length (entropy) to a list size that an eavesdropper has to resolve in order to recover a secret message. We provide explicit constructions of LSCs, and demonstrate that, when the source is uniformly distributed, the highest level of symbol secrecy for a fixed key length can be achieved through a construction based on minimum-distance separable (MDS) codes. Using an analysis related to rate-distortion theory, we then show how symbol secrecy can be used to determine the probability that an eavesdropper correctly reconstructs functions of the original plaintext. We illustrate how these bounds can be applied to characterize security properties of symmetric-key encryption schemes, and, in particular, extend security claims based on symbol secrecy to a functional setting.
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Venue: arXiv cs.SI 2015
Year: 2015

The average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse of the average distance, known as the (classic) closeness centrality of a node, is a popular importance measure in the study of social networks. We develop novel structural insights on the sparsifiability of the distance relation via weighted sampling. Based on that, we present highly practical algorithms with strong statistical guarantees for fundamental problems. We show that the average distance (and hence the centrality) for all nodes in a graph can be estimated using $O(ε^{-2})$ single-source distance computations. For a set $V$ of $n$ points in a metric space, we show that after preprocessing which uses $O(n)$ distance computations we can compute a weighted sample $S\subset V$ of size $O(ε^{-2})$ such that the average distance from any query point $v$ to $V$ can be estimated from the distances from $v$ to $S$. Finally, we show that for a set of points $V$ in a metric space, we can estimate the average pairwise distance using $O(n+ε^{-2})$ distance computations. The estimate is based on a weighted sample of $O(ε^{-2})$ pairs of points, which is computed using $O(n)$ distance computations. Our estimates are unbiased with normalized mean square error (NRMSE) of at most $ε$. Increasing the sample size by a $O(\log n)$ factor ensures that the probability that the relative error exceeds $ε$ is polynomially small.
Analysis of Clause set Schema Aided by Automated Theorem Proving: A Case Study [Extended Paper]
Venue: arXiv cs.LO 2015
Year: 2015

The schematic CERES method [8] is a recently developed method of cut elimination for proof schemata, that is a sequence of proofs with a recursive construction. Proof schemata can be thought of as a way to circumvent adding an induction rule to the LK-calculus. In this work, we formalize a schematic version of the infinitary pigeonhole principle, which we call the Non-injectivity Assertion schema (NiA-schema), in the LKS-calculus [8], and analyse the clause set schema extracted from the NiA-schema using some of the structure provided by the schematic CERES method. To the best of our knowledge, this is the first appli- cation of the constructs built for proof analysis of proof schemata to a mathematical argument since its publication. We discuss the role of Automated Theorem Proving (ATP) in schematic proof analysis, as well as the shortcomings of the schematic CERES method concerning the formalization of the NiA-schema, namely, the expressive power of the schematic resolution calculus. We conclude with a discussion concerning the usage of ATP in schematic proof analysis.
Pairs of Languages Closed under Shuffle Projection
Venue: arXiv cs.FL 2015
Year: 2015

Shuffle projection is motivated by the verification of safety properties of special parameterized systems. Basic definitions and properties, especially related to alphabetic homomorphisms, are presented. The relation between iterated shuffle products and shuffle projections is shown. A special class of multi-counter automata is introduced, to formulate shuffle projection in terms of computations of these automata represented by transductions. This reformulation of shuffle projection leads to construction principles for pairs of languages closed under shuffle projection. Additionally, it is shown that under certain conditions these transductions are rational, which implies decidability of closure against shuffle projection. Decidability of these conditions is proven for regular languages. Finally, without additional conditions, decidability of the question, whether a pair of regular languages is closed under shuffle projection, is shown. In an appendix the relation between shuffle projection and the shuffle product of two languages is discussed. Additionally, a kind of shuffle product for computations in S-automata is defined.
A Linear First-Order Functional Intermediate Language for Verified Compilers
Venue: arXiv cs.PL 2015
Year: 2015

We present the linear first-order intermediate language IL for verified compilers. IL is a functional language with calls to a nondeterministic environment. We give IL terms a second, imperative semantic interpretation and obtain a register transfer language. For the imperative interpretation we establish a notion of live variables. Based on live variables, we formulate a decidable property called coherence ensuring that the functional and the imperative interpretation of a term coincide. We formulate a register assignment algorithm for IL and prove its correctness. The algorithm translates a functional IL program into an equivalent imperative IL program. Correctness follows from the fact that the algorithm reaches a coherent program after consistently renaming local variables. We prove that the maximal number of live variables in the initial program bounds the number of different variables in the final coherent program. The entire development is formalized in Coq.
Channel Estimation in Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

We introduce novel blind and semi-blind channel estimation methods for cellular time-division duplexing systems with a large number of antennas at each base station. The methods are based on the maximum a-posteriori principle given a prior for the distribution of the channel vectors and the received signals from the uplink training and data phases. Contrary to the state-of-the-art massive MIMO channel estimators which either perform linear estimation based on the pilot symbols or rely on a blind principle, the proposed semi-blind method efficiently suppresses most of the interference caused by pilot-contamination. The simulative analysis illustrates that the semi-blind estimator outperforms state- of-the-art linear and non-linear approaches to the massive MIMO channel estimation problem.
A Preliminary Review of Influential Works in Data-Driven Discovery
Venue: arXiv cs.DL 2015
Year: 2015

The Gordon and Betty Moore Foundation ran an Investigator Competition as part of its Data-Driven Discovery Initiative in 2014. We received about 1,100 applications and each applicant had the opportunity to list up to five influential works in the general field of "Big Data" for scientific discovery. We collected nearly 5,000 references and 53 works were cited at least six times. This paper contains our preliminary findings.