OpenRaiser/Intern-Atlas huggingface dataset:
Improved Approximation Algorithms for Projection Games
Venue: arXiv cs.DS 2015
Year: 2015

The projection games (aka Label-Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label-Cover. In this paper we design several approximation algorithms for projection games: 1. A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar, Hajiaghayi and Karloff. 2. A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. 3. A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes.
Extortion under Uncertainty: Zero-Determinant Strategies in Noisy Games
Venue: arXiv cs.GT 2015
Year: 2015

Repeated game theory has been one of the most prevailing tools for understanding the long-run relationships, which are footstones in building human society. Recent works have revealed a new set of "zero-determinant (ZD)" strategies, which is an important advance in repeated games. A ZD strategy player can exert a unilaterally control on two players' payoffs. In particular he can deterministically set the opponent's payoff, or enforce an unfair linear relationship between the players' payoffs, thereby always seizing an advantageous share of payoffs. One of the limitations of the original ZD strategy, however, is that it does not capture the notion of robustness when the game is subjected to stochastic errors. In this paper, we propose a general model of ZD strategies for noisy repeated games, and find that ZD strategies have high robustness against errors. We further derive the pinning strategy under noise, by which the ZD strategy player coercively set the opponent's expected payoff to his desired level, although his payoff control ability declines with the increase of noise strength. Due to the uncertainty caused by noise, the ZD strategy player cannot secure his payoff to be higher than the opponent's, which implies strong extortions do not exist even under low noise. While we show that the ZD strategy player can still establish a novel kind of extortions, named weak extortions, where any increase of his own payoff always exceeds that of the opponent's by a fixed percentage, and the conditions under which the weak extortions can be realized are more stringent as the noise becomes stronger.
Strong inapproximability of the shortest reset word
Venue: arXiv cs.FL 2015
Year: 2015

The Černý conjecture states that every $n$-state synchronizing automaton has a reset word of length at most $(n-1)^2$. We study the hardness of finding short reset words. It is known that the exact version of the problem, i.e., finding the shortest reset word, is NP-hard and coNP-hard, and complete for the DP class, and that approximating the length of the shortest reset word within a factor of $O(\log n)$ is NP-hard [Gerbush and Heeringa, CIAA'10], even for the binary alphabet [Berlinkov, DLT'13]. We significantly improve on these results by showing that, for every $ε>0$, it is NP-hard to approximate the length of the shortest reset word within a factor of $n^{1-ε}$. This is essentially tight since a simple $O(n)$-approximation algorithm exists.
Incentives-Based Mechanism for Efficient Demand Response Programs
Venue: arXiv cs.GT 2015
Year: 2015

In this work we investigate the inefficiency of the electricity system with strategic agents. Specifically, we prove that without a proper control the total demand of an inefficient system is at most twice the total demand of the optimal outcome. We propose an incentives scheme that promotes optimal outcomes in the inefficient electricity market. The economic incentives can be seen as an indirect revelation mechanism that allocates resources using a one-dimensional message space per resource to be allocated. The mechanism does not request private information from users and is valid for any concave customer's valuation function. We propose a distributed implementation of the mechanism using population games and evaluate the performance of four popular dynamics methods in terms of the cost to implement the mechanism. We find that the achievement of efficiency in strategic environments might be achieved at a cost, which is dependent on both the users' preferences and the dynamic evolution of the system. Some simulation results illustrate the ideas presented throughout the paper.
Dependent Nonparametric Bayesian Group Dictionary Learning for online reconstruction of Dynamic MR images
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we introduce a dictionary learning based approach applied to the problem of real-time reconstruction of MR image sequences that are highly undersampled in k-space. Unlike traditional dictionary learning, our method integrates both global and patch-wise (local) sparsity information and incorporates some priori information into the reconstruction process. Moreover, we use a Dependent Hierarchical Beta-process as the prior for the group-based dictionary learning, which adaptively infers the dictionary size and the sparsity of each patch; and also ensures that similar patches are manifested in terms of similar dictionary atoms. An efficient numerical algorithm based on the alternating direction method of multipliers (ADMM) is also presented. Through extensive experimental results we show that our proposed method achieves superior reconstruction quality, compared to the other state-of-the- art DL-based methods.
Antenna Grouping based Feedback Compression for FDD-based Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Recent works on massive multiple-input multiple-output (MIMO) have shown that a potential breakthrough in capacity gains can be achieved by deploying a very large number of antennas at the basestation. In order to achieve the performance that massive MIMO systems promise, accurate transmit-side channel state information (CSI) should be available at the basestation. While transmit-side CSI can be obtained by employing channel reciprocity in time division duplexing (TDD) systems, explicit feedback of CSI from the user terminal to the basestation is needed for frequency division duplexing (FDD) systems. In this paper, we propose an antenna grouping based feedback reduction technique for FDD-based massive MIMO systems. The proposed algorithm, dubbed antenna group beamforming (AGB), maps multiple correlated antenna elements to a single representative value using pre-designed patterns. The proposed method modifies the feedback packet by introducing the concept of a header to select a suitable group pattern and a payload to quantize the reduced dimension channel vector. Simulation results show that the proposed method achieves significant feedback overhead reduction over conventional approach performing the vector quantization of whole channel vector under the same target sum rate requirement.
Almost every graph is divergent under the biclique operator
Venue: arXiv cs.DM 2015
Year: 2015

A biclique of a graph $G$ is a maximal induced complete bipartite subgraph of $G$. The biclique graph of $G$ denoted by $KB(G)$, is the intersection graph of all the bicliques of $G$. The biclique graph can be thought as an operator between graphs. The iterated biclique graph of $G$ denoted by $KB^{k}(G)$, is the graph obtained by applying the biclique operator $k$ successive times to $G$. The associated problem is deciding whether an input graph converges, diverges or is periodic under the biclique operator when $k$ grows to infinity. All possible behaviors were characterized recently and an $O(n^4)$ algorithm for deciding the behavior of any graph under the biclique operator was also given. In this work we prove new structural results of biclique graphs. In particular, we prove that every false-twin-free graph with at least $13$ vertices is divergent. These results lead to a linear time algorithm to solve the same problem.
Wavelet Trees Meet Suffix Trees
Venue: arXiv cs.DS 2015
Year: 2015

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size $σ\leq n$, our method builds the wavelet tree in $O(n \log σ/ \sqrt{\log{n}})$ time, improving upon the state-of-the-art algorithm by a factor of $\sqrt{\log n}$. As a consequence, given an array of n integers we can construct in $O(n \sqrt{\log n})$ time a data structure consisting of $O(n)$ machine words and capable of answering rank/select queries for the subranges of the array in $O(\log n / \log \log n)$ time. This is a $\log \log n$-factor improvement in query time compared to Chan and Pătraşcu and a $\sqrt{\log n}$-factor improvement in construction time compared to Brodal et al. Next, we switch to stringological context and propose a novel notion of wavelet suffix trees. For a string w of length n, this data structure occupies $O(n)$ words, takes $O(n \sqrt{\log n})$ time to construct, and simultaneously captures the combinatorial structure of substrings of w while enabling efficient top-down traversal and binary search. In particular, with a wavelet suffix tree we are able to answer in $O(\log |x|)$ time the following two natural analogues of rank/select queries for suffixes of substrings: for substrings x and y of w count the number of suffixes of x that are lexicographically smaller than y, and for a substring x of w and an integer k, find the k-th lexicographically smallest suffix of x. We further show that wavelet suffix trees allow to compute a run-length-encoded Burrows-Wheeler transform of a substring x of w in $O(s \log |x|)$ time, where s denotes the length of the resulting run-length encoding. This answers a question by Cormode and Muthukrishnan, who considered an analogous problem for Lempel-Ziv compression.
Long term Throughput and Approximate Capacity of Transmitter-Receiver Energy Harvesting Channel with Fading
Venue: arXiv cs.IT 2015
Year: 2015

We first consider an energy harvesting channel with fading, where only the transmitter harvests energy from natural sources. We bound the optimal long term throughput by a constant for a class of energy arrival distributions. The proposed method also gives a constant approximation to the capacity of the energy harvesting channel with fading. Next, we consider a more general system where both the transmitter and the receiver employ energy harvesting to power themselves. In this case, we show that finding an approximation to the optimal long term throughput is far more difficult, and identify a special case of unit battery capacity at both the transmitter and the receiver for which we obtain a universal bound on the ratio of the upper and lower bound on the long term throughput.
Cooperation with Disagreement Correction in the Presence of Communication Failures
Venue: arXiv cs.DC 2015
Year: 2015

Vehicle-to-vehicle communication is a fundamental requirement in cooperative vehicular systems to achieve high performance while keeping high safety standards. Vehicles periodically exchange critical information with nearby vehicles to determine their maneuvers according to the information quality and established strategies. However, wireless communication is prone to failures. Thus, participants can be unaware that other participants have not received the information on time resulting in conflicting trajectories that may not be safe. We present a deterministic solution that allows all participants to use a default strategy when other participants have not received on time the complete information. We base our solution on a timed distributed protocol that adapts its output according to the effect of message omission failures so that the disagreement period occurs for no longer than a constant time (of the order of milliseconds) that only depends on the message delay. We formally show the correctness and perform experiments to corroborate its efficiency. We explain how the proposed solution can be used on vehicular platooning to attain high performance and still guarantee high safety standards despite communication failures. We believe that this work can facilitate the implementation of cooperative driving systems that have to deal with inherent (communication) uncertainties.
An optimal algorithm for the weighted backup 2-center problem on a tree
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we are concerned with the weighted backup 2-center problem on a tree. The backup 2-center problem is a kind of center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a network. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum distance over all vertices to their closest functioning facility. In the weighted setting, each vertex in the network is associated with a nonnegative weight, and the distance from vertex $u$ to $v$ is weighted by the weight of $u$. With the strategy of prune-and-search, we propose a linear time algorithm, which is asymptotically optimal, to solve the weighted backup 2-center problem on a tree.
Approaches to Interpreter Composition
Venue: arXiv cs.PL 2015
Year: 2015

In this paper, we compose six different Python and Prolog VMs into 4 pairwise compositions: one using C interpreters; one running on the JVM; one using meta-tracing interpreters; and one using a C interpreter and a meta-tracing interpreter. We show that programs that cross the language barrier frequently execute faster in a meta-tracing composition, and that meta-tracing imposes a significantly lower overhead on composed programs relative to mono-language programs.
Network calculus for parallel processing
Venue: arXiv cs.PF 2015
Year: 2015

In this note, we present preliminary results on the use of "network calculus" for parallel processing systems, specifically MapReduce.
A Constrained-Dictionary version of LZ78 asymptotically achieves the Finite-State Compressibility for any Individual Sequence with a Distortion measure
Venue: arXiv cs.IT 2015
Year: 2015

The unrestricted LZ78 universal data-compression algorithm (as well as the LZ77 and LZW versions) achieves asymptotically, as the block-length tends to infinity, the FS compressibility, namely the best compression-ratio that may be achieved by any Information-lossless(IL) block-to-variable finite-state(FS) algorithm, for any infinitely-long individual sequence. The encoder parses the sequence into distinct phrases where each newly generated phrase is a past phrase which is already stored in a dictionary, extended by one letter. The newly generated phrase is then added to the updated, ever-growing dictionary. One heuristic approach is the "Least Recently Utilized" (LRU) deletion approach, where only the most recent D entries are kept in the dictionary, thus yielding a constrained-dictionary version of LZ78 denoted by LZ78(LRU). In this note, for the sake of completeness, it is demonstrated again via a simple proof that the unrestricted LZ78 algorithm asymptotically achieves the FS-Compressibility. Then, it is demonstrated that the LZ78(LRU) information-lossless data-compression algorithm also achieves the FS compressibility, as the dictionary size D tends to infinity. Although this is perhaps not surprising, it does nevertheless yield a theoretical optimality argument for the popular LZ78(LRU) algorithm (and similarly, for the LZW(LRU) algorithm). In addition, the finite-state compressibility of an individual sequence under a constrained allowable distance measure between the original sequence and the decompressed sequence is defined. It is demonstrated that a particular adaptive vector-quantizer that sequentially replaces clusters of L-vectors onto a single, cluster-representative L-vector, followed by a constrained D-entries-dictionary version of LZ78(LRU) as above, is asymptotically optimal as D tends to infinity and L= log D .
Power Estimation in LTE systems with the General Framework of Standard Interference Mappings
Venue: arXiv cs.IT 2015
Year: 2015

We devise novel techniques to obtain the downlink power inducing a given load in long-term evolution (LTE) systems, where we define load as the fraction of resource blocks in the time-frequency grid being requested by users from a given base station. These techniques are particularly important because previous studies have proved that the data rate requirement of users can be satisfied with lower transmit energy if we allow the load to increase. Those studies have also shown that obtaining the power assignment from a desired load profile can be posed as a fixed point problem involving standard interference mappings, but so far the mappings have not been obtained explicitly. One of our main contributions in this study is to close this gap. We derive an interference mapping having as its fixed point the power assignment inducing a desired load, assuming that such an assignment exists. Having this mapping in closed form, we simplify the proof of the aforementioned known results, and we also devise novel iterative algorithms for power computation that have many numerical advantages over previous methods.
Collaborative Deep Learning for Recommender Systems
Venue: arXiv cs.LG 2015
Year: 2015

Collaborative filtering (CF) is a successful approach commonly used by many recommender systems. Conventional CF-based methods use the ratings given to items by users as the sole source of information for learning to make recommendation. However, the ratings are often very sparse in many applications, causing CF-based methods to degrade significantly in their recommendation performance. To address this sparsity problem, auxiliary information such as item content information may be utilized. Collaborative topic regression (CTR) is an appealing recent method taking this approach which tightly couples the two components that learn from two different sources of information. Nevertheless, the latent representation learned by CTR may not be very effective when the auxiliary information is very sparse. To address this problem, we generalize recent advances in deep learning from i.i.d. input to non-i.i.d. (CF-based) input and propose in this paper a hierarchical Bayesian model called collaborative deep learning (CDL), which jointly performs deep representation learning for the content information and collaborative filtering for the ratings (feedback) matrix. Extensive experiments on three real-world datasets from different domains show that CDL can significantly advance the state of the art.
The Ordered Weighted $\ell_1$ Norm: Atomic Formulation, Projections, and Algorithms
Venue: arXiv cs.DS 2015
Year: 2015

The ordered weighted $\ell_1$ norm (OWL) was recently proposed, with two different motivations: its good statistical properties as a sparsity promoting regularizer; the fact that it generalizes the so-called {\it octagonal shrinkage and clustering algorithm for regression} (OSCAR), which has the ability to cluster/group regression variables that are highly correlated. This paper contains several contributions to the study and application of OWL regularization: the derivation of the atomic formulation of the OWL norm; the derivation of the dual of the OWL norm, based on its atomic formulation; a new and simpler derivation of the proximity operator of the OWL norm; an efficient scheme to compute the Euclidean projection onto an OWL ball; the instantiation of the conditional gradient (CG, also known as Frank-Wolfe) algorithm for linear regression problems under OWL regularization; the instantiation of accelerated projected gradient algorithms for the same class of problems. Finally, a set of experiments give evidence that accelerated projected gradient algorithms are considerably faster than CG, for the class of problems considered.
Second-Order Propositional Satisfiability
Venue: arXiv cs.LO 2015
Year: 2015

Fundamentally, every static program analyser searches for a proof through a combination of heuristics providing candidate solutions and a candidate validation technique. Essentially, the heuristic reduces a second-order problem to a first-order/propositional one, while the validation is often just a call to a SAT/SMT solver. This results in a monolithic design of such analyses that conflates the formulation of the problem with the solving process. Consequently, any change to the latter causes changes to the whole analysis. This design is dictated by the state of the art in solver technology. While SAT/SMT solvers have experienced tremendous progress, there are barely any second-order solvers. This paper takes a step towards addressing this situation by proposing a decidable fragment of second-order logic that is still expressive enough to capture numerous program analysis problems (e.g. safety proving, bug finding, termination and non-termination proving, superoptimisation). We refer to the satisfiability problem for this fragment as Second-Order SAT and show it is NEXPTIME-complete. Finally, we build a decision procedure for Second-Order SAT based on program synthesis and present experimental evidence that our approach is tractable for program analysis problems.
Fast Low-rank Representation based Spatial Pyramid Matching for Image Classification
Venue: arXiv cs.CV 2015
Year: 2015

Spatial Pyramid Matching (SPM) and its variants have achieved a lot of success in image classification. The main difference among them is their encoding schemes. For example, ScSPM incorporates Sparse Code (SC) instead of Vector Quantization (VQ) into the framework of SPM. Although the methods achieve a higher recognition rate than the traditional SPM, they consume more time to encode the local descriptors extracted from the image. In this paper, we propose using Low Rank Representation (LRR) to encode the descriptors under the framework of SPM. Different from SC, LRR considers the group effect among data points instead of sparsity. Benefiting from this property, the proposed method (i.e., LrrSPM) can offer a better performance. To further improve the generalizability and robustness, we reformulate the rank-minimization problem as a truncated projection problem. Extensive experimental studies show that LrrSPM is more efficient than its counterparts (e.g., ScSPM) while achieving competitive recognition rates on nine image data sets.
2-Vertex Connectivity in Directed Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We complement our study of 2-connectivity in directed graphs, by considering the computation of the following 2-vertex-connectivity relations: We say that two vertices v and w are 2-vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v. We also say that v and w are vertex-resilient if the removal of any vertex different from v and w leaves v and w in the same strongly connected component. We show how to compute the above relations in linear time so that we can report in constant time if two vertices are 2-vertex-connected or if they are vertex-resilient. We also show how to compute in linear time a sparse certificate for these relations, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-vertex-connectivity and vertex-resilience relations as the input graph, where n is the number of vertices.