OpenRaiser/Intern-Atlas huggingface dataset:
Duality of a Source Coding Problem and the Semi-Deterministic Broadcast Channel with Rate-Limited Cooperation
Venue: arXiv cs.IT 2016
Year: 2016

The Wyner-Ahlswede-Körner (WAK) empirical-coordination problem where the encoders cooperate via a finite-capacity one-sided link is considered. The coordination-capacity region is derived by combining several source coding techniques, such as Wyner-Ziv (WZ) coding, binning and superposition coding. Furthermore, a semi-deterministic (SD) broadcast channel (BC) with one-sided decoder cooperation is considered. Duality principles relating the two problems are presented, and the capacity region for the SD-BC setting is derived. The direct part follows from an achievable region for a general BC that is tight for the SD scenario. A converse is established by using telescoping identities. The SD-BC is shown to be operationally equivalent to a class of relay-BCs (RBCs) and the correspondence between their capacity regions is established. The capacity region of the SD-BC is transformed into an equivalent region that is shown to be dual to the admissible region of the WAK problem in the sense that the information measures defining the corner points of both regions coincide. Achievability and converse proofs for the equivalent region are provided. For the converse, we use a probabilistic construction of auxiliary random variables that depends on the distribution induced by the codebook. Several examples illustrate the results.
Cascading A*: a Parallel Approach to Approximate Heuristic Search
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we proposed a new approximate heuristic search algorithm: Cascading A*, which is a two-phrase algorithm combining A* and IDA* by a new concept "envelope ball". The new algorithm CA* is efficient, able to generate approximate solution and any-time solution, and parallel friendly.
An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization
Venue: arXiv cs.DS 2016
Year: 2016

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires \emph{positive} correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables. The recent breakthrough of Li & Svensson for the classical $k$-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for $k$-median from $2.732 + ε$ to $2.675 + ε$ by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter $ε$ from Li-Svensson's $N^{O(1/ε^2)}$ to $N^{O((1/ε) \log(1/ε))}$.
From Denoising to Compressed Sensing
Venue: arXiv cs.IT 2016
Year: 2016

A denoising algorithm seeks to remove noise, errors, or perturbations from a signal. Extensive research has been devoted to this arena over the last several decades, and as a result, today's denoisers can effectively remove large amounts of additive white Gaussian noise. A compressed sensing (CS) reconstruction algorithm seeks to recover a structured signal acquired using a small number of randomized measurements. Typical CS reconstruction algorithms can be cast as iteratively estimating a signal from a perturbed observation. This paper answers a natural question: How can one effectively employ a generic denoiser in a CS reconstruction algorithm? In response, we develop an extension of the approximate message passing (AMP) framework, called Denoising-based AMP (D-AMP), that can integrate a wide class of denoisers within its iterations. We demonstrate that, when used with a high performance denoiser for natural images, D-AMP offers state-of-the-art CS recovery performance while operating tens of times faster than competing methods. We explain the exceptional performance of D-AMP by analyzing some of its theoretical features. A key element in D-AMP is the use of an appropriate Onsager correction term in its iterations, which coerces the signal perturbation at each iteration to be very close to the white Gaussian noise that denoisers are typically designed to remove.
Z2Z4-additive cyclic codes, generator polynomials and dual codes
Venue: arXiv cs.DM 2016
Year: 2016

A ${\mathbb{Z}}_2{\mathbb{Z}}_4$-additive code ${\cal C}\subseteq{\mathbb{Z}}_2^α\times{\mathbb{Z}}_4^β$ is called cyclic if the set of coordinates can be partitioned into two subsets, the set of ${\mathbb{Z}}_2$ and the set of ${\mathbb{Z}}_4$ coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. These codes can be identified as submodules of the $\mathbb{Z}_4[x]$-module $\mathbb{Z}_2[x]/(x^α-1)\times\mathbb{Z}_4[x]/(x^β-1)$. The parameters of a ${\mathbb{Z}}_2{\mathbb{Z}}_4$-additive cyclic code are stated in terms of the degrees of the generator polynomials of the code. The generator polynomials of the dual code of a ${\mathbb{Z}}_2{\mathbb{Z}}_4$-additive cyclic code are determined in terms of the generator polynomials of the code ${\cal C}$.
Single-Peaked Consistency for Weak Orders Is Easy
Venue: arXiv cs.GT 2016
Year: 2016

In economics and social choice single-peakedness is one of the most important and commonly studied models for preferences. It is well known that single-peaked consistency for total orders is in P. However in practice a preference profile is not always comprised of total orders. Often voters have indifference between some of the candidates. In a weak preference order indifference must be transitive. We show that single-peaked consistency for weak orders is in P for three different variants of single-peakedness for weak orders. Specifically, we consider Black's original definition of single-peakedness for weak orders, Black's definition of single-plateaued preferences, and the existential model recently introduced by Lackner. We accomplish our results by transforming each of these single-peaked consistency problems to the problem of determining if a 0-1 matrix has the consecutive ones property.
Nowcasting the Bitcoin Market with Twitter Signals
Venue: arXiv cs.SI 2016
Year: 2016

This paper analyzes correlations and causalities between Bitcoin market indicators and Twitter posts containing emotional signals on Bitcoin. Within a timeframe of 104 days (November 23rd 2013 - March 7th 2014), about 160,000 Twitter posts containing "bitcoin" and a positive, negative or uncertainty related term were collected and further analyzed. For instance, the terms "happy", "love", "fun", "good", "bad", "sad" and "unhappy" represent positive and negative emotional signals, while "hope", "fear" and "worry" are considered as indicators of uncertainty. The static (daily) Pearson correlation results show a significant positive correlation between emotional tweets and the close price, trading volume and intraday price spread of Bitcoin. However, a dynamic Granger causality analysis does not confirm a statistically significant effect of emotional Tweets on Bitcoin market values. To the contrary, the analyzed data shows that a higher Bitcoin trading volume Granger causes more signals of uncertainty within a 24 to 72-hour timeframe. This result leads to the interpretation that emotional sentiments rather mirror the market than that they make it predictable. Finally, the conclusion of this paper is that the microblogging platform Twitter is Bitcoin's virtual trading floor, emotionally reflecting its trading dynamics.
On the Average-case Complexity of Pattern Matching with Wildcards
Venue: arXiv cs.DS 2016
Year: 2016

Pattern matching with wildcards is the problem of finding all factors of a text $t$ of length $n$ that match a pattern $x$ of length $m$, where wildcards (characters that match everything) may be present. In this paper we present a number of fast average-case algorithms for pattern matching where wildcards are restricted to either the pattern or the text, however, the results are easily adapted to the case where wildcards are allowed in both. We analyse the \textit{average-case} complexity of these algorithms and show the first non-trivial time bounds. These are the first results on the average-case complexity of pattern matching with wildcards which, as a by product, provide with first provable separation in complexity between exact pattern matching and pattern matching with wildcards in the word RAM model.
A Centralized Mechanism to Make Predictions Based on Data From Multiple WSNs
Venue: arXiv cs.NI 2016
Year: 2016

In this work, we present a method that exploits a scenario with inter-Wireless Sensor Networks (WSNs) information exchange by making predictions and adapting the workload of a WSN according to their outcomes. We show the feasibility of an approach that intelligently utilizes information produced by other WSNs that may or not belong to the same administrative domain. To illustrate how the predictions using data from external WSNs can be utilized, a specific use-case is considered, where the operation of a WSN measuring relative humidity is optimized using the data obtained from a WSN measuring temperature. Based on a dedicated performance score, the simulation results show that this new approach can find the optimal operating point associated to the trade-off between energy consumption and quality of measurements. Moreover, we outline the additional challenges that need to be overcome, and draw conclusions to guide the future work in this field.
Discovering Beaten Paths in Collaborative Ontology-Engineering Projects using Markov Chains
Venue: arXiv cs.SI 2016
Year: 2016

Biomedical taxonomies, thesauri and ontologies in the form of the International Classification of Diseases (ICD) as a taxonomy or the National Cancer Institute Thesaurus as an OWL-based ontology, play a critical role in acquiring, representing and processing information about human health. With increasing adoption and relevance, biomedical ontologies have also significantly increased in size. For example, the 11th revision of the ICD, which is currently under active development by the WHO contains nearly 50,000 classes representing a vast variety of different diseases and causes of death. This evolution in terms of size was accompanied by an evolution in the way ontologies are engineered. Because no single individual has the expertise to develop such large-scale ontologies, ontology-engineering projects have evolved from small-scale efforts involving just a few domain experts to large-scale projects that require effective collaboration between dozens or even hundreds of experts, practitioners and other stakeholders. Understanding how these stakeholders collaborate will enable us to improve editing environments that support such collaborations. We uncover how large ontology-engineering projects, such as the ICD in its 11th revision, unfold by analyzing usage logs of five different biomedical ontology-engineering projects of varying sizes and scopes using Markov chains. We discover intriguing interaction patterns (e.g., which properties users subsequently change) that suggest that large collaborative ontology-engineering projects are governed by a few general principles that determine and drive development. From our analysis, we identify commonalities and differences between different projects that have implications for project managers, ontology editors, developers and contributors working on collaborative ontology-engineering projects and tools in the biomedical domain.
Multichannel group sparsity methods for compressive channel estimation in doubly selective multicarrier MIMO systems (extended version)
Venue: arXiv cs.IT 2016
Year: 2016

We consider channel estimation within pulse-shaping multicarrier multiple-input multiple-output (MIMO) systems transmitting over doubly selective MIMO channels. This setup includes MIMO orthogonal frequency-division multiplexing (MIMO-OFDM) systems as a special case. We show that the component channels tend to exhibit an approximate joint group sparsity structure in the delay-Doppler domain. We then develop a compressive channel estimator that exploits this structure for improved performance. The proposed channel estimator uses the methodology of multichannel group sparse compressed sensing, which combines the methodologies of group sparse compressed sensing and multichannel compressed sensing. We derive an upper bound on the channel estimation error and analyze the estimator's computational complexity. The performance of the estimator is further improved by introducing a basis expansion yielding enhanced joint group sparsity, along with a basis optimization algorithm that is able to utilize prior statistical information if available. Simulations using a geometry-based channel simulator demonstrate the performance gains due to leveraging the joint group sparsity and optimizing the basis.
Inferring Loop Invariants by Mutation, Dynamic Analysis, and Static Checking
Venue: arXiv cs.SE 2016
Year: 2016

Verifiers that can prove programs correct against their full functional specification require, for programs with loops, additional annotations in the form of loop invariants---propeties that hold for every iteration of a loop. We show that significant loop invariant candidates can be generated by systematically mutating postconditions; then, dynamic checking (based on automatically generated tests) weeds out invalid candidates, and static checking selects provably valid ones. We present a framework that automatically applies these techniques to support a program prover, paving the way for fully automatic verification without manually written loop invariants: Applied to 28 methods (including 39 different loops) from various java.util classes (occasionally modified to avoid using Java features not fully supported by the static checker), our DYNAMATE prototype automatically discharged 97% of all proof obligations, resulting in automatic complete correctness proofs of 25 out of the 28 methods---outperforming several state-of-the-art tools for fully automatic verification.
The Power of Two Choices with Simple Tabulation
Venue: arXiv cs.DS 2016
Year: 2016

The power of two choices is a classic paradigm for load balancing when assigning $m$ balls to $n$ bins. When placing a ball, we pick two bins according to two hash functions $h_0$ and $h_1$, and place the ball in the least loaded bin. Assuming fully random hash functions, when $m=O(n)$, Azar et al.~[STOC'94] proved that the maximum load is $\lg \lg n + O(1)$ with high probability. In this paper, we investigate the power of two choices when the hash functions $h_0$ and $h_1$ are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM'12], Pǎtraşcu and Thorup claimed that the expected maximum load with simple tabulation is $O(\lg\lg n)$. This did not include any high probability guarantee, so the load balancing was not yet to be trusted. Here, we show that with simple tabulation, the maximum load is $O(\lg\lg n)$ with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by $\lg \lg n + O(1)$, or even $(1+o(1))\lg \lg n$ with high probability. Finally, we show that the expected maximum load is $\lg \lg n + O(1)$, just like with fully random hashing.
Distributed and Fair Beaconing Rate Adaptation for Congestion Control in Vehicular Networks
Venue: arXiv cs.NI 2016
Year: 2016

Cooperative inter-vehicular applications rely on the exchange of broadcast single-hop status messages among vehicles, called beacons. The aggregated load on the wireless channel due to periodic beacons can prevent the transmission of other types of messages, what is called channel congestion due to beaconing activity. In this paper we approach the problem of controlling the beaconing rate on each vehicle by modeling it as a Network Utility Maximization (NUM) problem. This allows us to formally apply the notion of fairness of a beaconing rate allocation in vehicular networks and to control the trade-off between efficiency and fairness. The NUM methodology provides a rigorous framework to design a broad family of simple and decentralized algorithms, with proved convergence guarantees to a fair allocation solution. In this context, we focus exclusively in beaconing rate control and propose the Fair Adaptive Beaconing Rate for Intervehicular Communications (FABRIC) algorithm, which uses a particular scaled gradient projection algorithm to solve the dual of the NUM problem. The desired fairness notion in the allocation can be established with an algorithm parameter. Simulation results validate our approach and show that FABRIC converges to fair rate allocations in multi-hop and dynamic scenarios.
A 3-factor approximation algorithm for a Maximum Acyclic Agreement Forest on k rooted, binary phylogenetic trees
Venue: arXiv cs.DS 2016
Year: 2016

Phylogenetic trees are leaf-labelled trees, where the leaves correspond to extant species (taxa), and the internal vertices represent ancestral species. The evolutionary history of a set of species can be explained by more than one phylogenetic tree, giving rise to the problem of comparing phylogenetic trees for similarity. Various distance metrics, like the subtree prune-and-regraft (SPR), tree bisection reconnection (TBR) and nearest neighbour interchange (NNI) have been proposed to capture this similarity. The distance between two phylogenetic trees can also be measured by the size of a Maximum Agreement Forest (MAF) on these trees, as it has been shown that the rooted subtree prune-and-regraft distance is 1 less than the size of a MAF. Since computing a MAF of minimum size is an NP-hard problem, approximation algorithms are of interest. Recently, it has been shown that the MAF on k(>=2) trees can be approximated to within a factor of 8. In this paper, we improve this ratio to 3. For certain species, however, the evolutionary history is not completely tree-like. Due to reticulate evolution two gene trees, though related, appear different, making a phylogenetic network a more appropriate representation of reticulate evolution. A phylogenetic network contains hybrid nodes for the species evolved from two parents. The number of such nodes is its hybridization number. It has been shown that this number is 1 less than the size of a Maximum Acyclic Agreement Forest (MAAF). We show that the MAAF for k(>= 2) phylogenetic trees can be approximated to within a factor of 3.
Level-based Analysis of Genetic Algorithms and other Search Processes
Venue: arXiv cs.NE 2016
Year: 2016

Understanding how the time-complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time-complexity results concern simplified EAs, such as the (1+1) EA. This paper describes the level-based theorem, a new technique tailored to population-based processes. It applies to any non-elitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. We demonstrate the technique on several pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimisation. The conditions of the theorem are often straightforward to verify, even for Genetic Algorithms and Estimation of Distribution Algorithms which were considered highly non-trivial to analyse. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.
On MultiAspect Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Different graph generalizations have been recently used in an ad-hoc manner to represent multilayer networks, i.e. systems formed by distinct layers where each layer can be seen as a network. Similar constructions have also been used to represent time-varying networks. We introduce the concept of MultiAspect Graph (MAG) as a graph generalization that we prove to be isomorphic to a directed graph, and also capable of representing all previous generalizations. In our proposal, the set of vertices, layers, time instants, or any other independent features are considered as an aspect of the MAG. For instance, a MAG is able to represent multilayer or time-varying networks, while both concepts can also be combined to represent a multilayer time-varying network and even other higher-order networks. Since the MAG structure admits an arbitrary (finite) number of aspects, it hence introduces a powerful modelling abstraction for networked complex systems. This paper formalizes the concept of MAG and derives theoretical results useful in the analysis of complex networked systems modelled using the proposed MAG abstraction. We also present an overview of the MAG applicability.
Estimating Renyi Entropy of Discrete Distributions
Venue: arXiv cs.IT 2016
Year: 2016

It was recently shown that estimating the Shannon entropy $H({\rm p})$ of a discrete $k$-symbol distribution ${\rm p}$ requires $Θ(k/\log k)$ samples, a number that grows near-linearly in the support size. In many applications $H({\rm p})$ can be replaced by the more general Rényi entropy of order $α$, $H_α({\rm p})$. We determine the number of samples needed to estimate $H_α({\rm p})$ for all $α$, showing that $α< 1$ requires a super-linear, roughly $k^{1/α}$ samples, noninteger $α>1$ requires a near-linear $k$ samples, but, perhaps surprisingly, integer $α>1$ requires only $Θ(k^{1-1/α})$ samples. Furthermore, developing on a recently established connection between polynomial approximation and estimation of additive functions of the form $\sum_{x} f({\rm p}_x)$, we reduce the sample complexity for noninteger values of $α$ by a factor of $\log k$ compared to the empirical estimator. The estimators achieving these bounds are simple and run in time linear in the number of samples. Our lower bounds provide explicit constructions of distributions with different Rényi entropies that are hard to distinguish.
Location Prediction: Communities Speak Louder than Friends
Venue: arXiv cs.SI 2016
Year: 2016

Humans are social animals, they interact with different communities of friends to conduct different activities. The literature shows that human mobility is constrained by their social relations. In this paper, we investigate the social impact of a person's communities on his mobility, instead of all friends from his online social networks. This study can be particularly useful, as certain social behaviors are influenced by specific communities but not all friends. To achieve our goal, we first develop a measure to characterize a person's social diversity, which we term `community entropy'. Through analysis of two real-life datasets, we demonstrate that a person's mobility is influenced only by a small fraction of his communities and the influence depends on the social contexts of the communities. We then exploit machine learning techniques to predict users' future movement based on their communities' information. Extensive experiments demonstrate the prediction's effectiveness.