OpenRaiser/Intern-Atlas huggingface dataset:
The Rate-Distortion Function and Excess-Distortion Exponent of Sparse Regression Codes with Optimal Encoding
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the performance of sparse regression codes for lossy compression with the squared-error distortion criterion. In a sparse regression code, codewords are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding, sparse regression codes achieve the Shannon rate-distortion function for i.i.d. Gaussian sources $R^*(D)$ as well as the optimal excess-distortion exponent. This completes a previous result which showed that $R^*(D)$ and the optimal exponent were achievable for distortions below a certain threshold. The proof of the rate-distortion result is based on the second moment method, a popular technique to show that a non-negative random variable $X$ is strictly positive with high probability. In our context, $X$ is the number of codewords within target distortion $D$ of the source sequence. We first identify the reason behind the failure of the standard second moment method for certain distortions, and illustrate the different failure modes via a stylized example. We then use a refinement of the second moment method to show that $R^*(D)$ is achievable for all distortion values. Finally, the refinement technique is applied to Suen's correlation inequality to prove the achievability of the optimal Gaussian excess-distortion exponent.
Design of Symbolic Controllers for Networked Control Systems
Venue: arXiv cs.SY 2017
Year: 2017

Networked Control Systems (NCS) are distributed systems where plants, sensors, actuators and controllers communicate over shared networks. Non-ideal behaviors of the communication network include variable sampling/transmission intervals and communication delays, packet losses, communication constraints and quantization errors. NCS have been the object of intensive study in the last few years. However, due to the inherent complexity of NCS, current literature focuses on a subset of these non-idealities and mostly considers stability and stabilizability problems. Recent technology advances need different and more complex control objectives to be considered. In this paper we present first a general model of NCS, including most relevant non-idealities of the communication network; then, we propose a symbolic model approach to the control design with objectives expressed in terms of non-deterministic transition systems. The presented results are based on recent advances in symbolic control design of continuous and hybrid systems. An example in the context of robot motion planning with remote control is included, showing the effectiveness of the proposed approach.
Analysis of d-Hop Dominating Set Problem for Directed Graph with Indegree Bounded by One
Venue: arXiv cs.DS 2017
Year: 2017

Efficient communication between nodes in ad-hoc networks can be established through repeated cluster formations with designated \textit{cluster-heads}. In this context minimum d-hop dominating set problem was introduced for cluster formation in ad-hoc networks and is proved to be NP-complete. Hence, an exact solution to this problem for certain subclass of graphs (representing an ad-hoc network) can be beneficial. In this short paper we perform computational complexity analysis of minimum d-hop dominating set problem for directed graphs with in-degree bounded by $1$. The optimum solution of the problem can be found polynomially by exploiting certain properties of the graph under consideration. For a digraph $G_{D}=(V_D,E_D)$ an $\mathcal{O}(|V_D|^2)$ solution is provided to the problem.
Binary Fading Interference Channel with No CSIT
Venue: arXiv cs.IT 2017
Year: 2017

We study the capacity region of the two-user Binary Fading (or Erasure) Interference Channel where the transmitters have no knowledge of the channel state information. We develop new inner-bounds and outer-bounds for this problem. We identify three regimes based on the channel parameters: weak, moderate, and strong interference regimes. Interestingly, this is similar to the generalized degrees of freedom of the two-user Gaussian interference channel where transmitters have perfect channel knowledge. We show that for the weak interference regime, treating interference as erasure is optimal while for the strong interference regime, decoding interference is optimal. For the moderate interference regime, we provide new inner and outer bounds. The inner-bound is based on a modification of the Han-Kobayashi scheme for the erasure channel, enhanced by time-sharing. We study the gap between our inner-bound and our outer-bounds for the moderate interference regime and compare our results to that of the Gaussian interference channel. Deriving our new outer-bounds has three main steps. We first create a contracted channel that has fewer states compared to the original channel, in order to make the analysis tractable. We then prove the Correlation Lemma that shows an outer-bound on the capacity region of the contracted channel also serves as an outer-bound for the original channel. Finally using the Conditional Entropy Leakage Lemma, we derive our outer-bound on the capacity region of the contracted channel.
Coded Random Access: Applying Codes on Graphs to Design Random Access Protocols
Venue: arXiv cs.NI 2017
Year: 2017

The rise of machine-to-machine communications has rekindled the interest in random access protocols as a support for a massive number of uncoordinatedly transmitting devices. The legacy ALOHA approach is developed under a collision model, where slots containing collided packets are considered as waste. However, if the common receiver (e.g., base station) is capable to store the collision slots and use them in a transmission recovery process based on successive interference cancellation, the design space for access protocols is radically expanded. We present the paradigm of coded random access, in which the structure of the access protocol can be mapped to a structure of an erasure-correcting code defined on graph. This opens the possibility to use coding theory and tools for designing efficient random access protocols, offering markedly better performance than ALOHA. Several instances of coded random access protocols are described, as well as a case study on how to upgrade a legacy ALOHA system using the ideas of coded random access.
Fast, Responsive Decentralised Graph Colouring
Venue: arXiv cs.DS 2017
Year: 2017

We solve, in a fully decentralised way (\ie with no message passing), the classic problem of colouring a graph. We propose a novel algorithm that is automatically responsive to topology changes, and we prove that it converges quickly to a proper colouring in $O(N\log{N})$ time with high probability for generic graphs (and in $O(\log{N})$ time if $Δ=O(1)$) when the number of available colours is greater than $Δ$, the maximum degree of the graph. We believe the proof techniques used in this work are of independent interest and provide new insight into the properties required to ensure fast convergence of decentralised algorithms.
Trade-offs in School Choice: Comparing Deferred Acceptance, the Naive and the Classic Boston Mechanism
Venue: arXiv cs.GT 2017
Year: 2017

The three most common school choice mechanisms are the Deferred Acceptance mechanism (DA), the classic Boston mechanism (BM), and a variant of the Boston mechanism where students automatically skip exhausted schools, which we call the adaptive Boston mechanism (ABM). Assuming truthful reporting, we compare student welfare under these mechanisms both from a conceptual and from a quantitative perspective: We first show that, BM rank dominates DA whenever they are comparable; and via limit arguments and simulations we show that ABM yields intermediate student welfare between BM and DA. Second, we perform computational experiments with preference data from the high school match in Mexico City. We find that student welfare (in terms of rank transitions) is highest under BM, intermediate under ABM, and lowest under DA. BM, ABM, and DA can thus be understood to form a hierarchy in terms of student welfare. In contrast, in (Mennle and Seuken, 2017), we have found that the same mechanisms also form a hierarchy in terms of incentives for truthtelling that points in the opposite direction. A decision between them therefore involves an implicit trade-off between incentives and student welfare.
Cryptocurrencies without Proof of Work
Venue: arXiv cs.CR 2017
Year: 2017

We study decentralized cryptocurrency protocols in which the participants do not deplete physical scarce resources. Such protocols commonly rely on Proof of Stake, i.e., on mechanisms that extend voting power to the stakeholders of the system. We offer analysis of existing protocols that have a substantial amount of popularity. We then present our novel pure Proof of Stake protocols, and argue that they help in mitigating problems that the existing protocols exhibit.
The Rise of Social Bots
Venue: arXiv cs.SI 2017
Year: 2017

The Turing test aimed to recognize the behavior of a human from that of a computer algorithm. Such challenge is more relevant than ever in today's social media context, where limited attention and technology constrain the expressive power of humans, while incentives abound to develop software agents mimicking humans. These social bots interact, often unnoticed, with real people in social media ecosystems, but their abundance is uncertain. While many bots are benign, one can design harmful bots with the goals of persuading, smearing, or deceiving. Here we discuss the characteristics of modern, sophisticated social bots, and how their presence can endanger online ecosystems and our society. We then review current efforts to detect social bots on Twitter. Features related to content, network, sentiment, and temporal patterns of activity are imitated by bots but at the same time can help discriminate synthetic behaviors from human ones, yielding signatures of engineered social tampering.
Distributed Computing by Mobile Robots: Uniform Circle Formation
Venue: arXiv cs.DC 2017
Year: 2017

Consider a set of $n$ simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular $n$-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant.
AFP Algorithm and a Canonical Normal Form for Horn Formulas
Venue: arXiv cs.LG 2017
Year: 2017

AFP Algorithm is a learning algorithm for Horn formulas. We show that it does not improve the complexity of AFP Algorithm, if after each negative counterexample more that just one refinements are performed. Moreover, a canonical normal form for Horn formulas is presented, and it is proved that the output formula of AFP Algorithm is in this normal form.
Facilitating adoption of Internet technologies and services with externalities via cost subsidization
Venue: arXiv cs.SI 2017
Year: 2017

This paper models the temporal adoption dynamics of an abstracted Internet technology or service, where the instantaneous net value of the service perceived by each (current or potential) user / customer incorporates three key features: i) user service affinity heterogeneity, ii) a network externality, and iii) a subscription cost. Internet technologies and services with network externalities face a "chicken and egg" adoption problem in that the service requires an established customer base in order to attract new customers. In this paper we study cost subsidization as a means to "reach the knee", at which point the externality drives rapid service adoption, and thereby change the equilibrium service fractional adoption level from an initial near-zero level to a final near-one level (full adoption). We present three simple subsidy models and evaluate them under two natural performance metrics: i) the duration required for the subsidized service to reach a given target adoption level, and ii) the aggregate cost of the subsidy born by the service provide. First, we present a "two target adoption subsidy" (TTAS) that subsidizes the cost so as to keep the fraction of users with positive net utility at a (constant) target level until the actual adoption target is reached. Second, we study a special case of the above where the target ensures all users have positive net utility, corresponding to a "quickest adoption" subsidy (QAS). Third, we introduce an approximation of QAS, called AQAS, that only requires the service provider adjust the subsidy level a prescribed number of times. Fourth, we study equilibria and their stability under uniformly and normally distributed user service affinities, highlighting the unstable equilibrium in each case as the natural target adoption level for the provider. Finally, we provide a fictional case study to illustrate the results.
On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
Venue: arXiv cs.IT 2017
Year: 2017

In estimating frequencies given that the signal waveforms are undersampled multiple times, Xia et. al. proposed to use a generalized version of Chinese remainder Theorem (CRT), where the moduli are $M_1, M_2, \cdots, M_k$ which are not necessarily pairwise coprime. If the errors of the corrupted remainders are within $τ=\sds \max_{1\le i\le k} \min_{\stackrel{1\le j\le k}{j\neq i}} \frac{\gcd(M_i,M_j)}4$, their schemes can be used to construct an approximation of the solution to the generalized CRT with an error smaller than $τ$. Accurately finding the quotients is a critical ingredient in their approach. In this paper, we shall start with a faithful historical account of the generalized CRT. We then present two treatments of the problem of solving generalized CRT with erroneous remainders. The first treatment follows the route of Wang and Xia to find the quotients, but with a simplified process. The second treatment considers a simplified model of generalized CRT and takes a different approach by working on the corrupted remainders directly. This approach also reveals some useful information about the remainders by inspecting extreme values of the erroneous remainders modulo $4τ$. Both of our treatments produce efficient algorithms with essentially optimal performance. Finally, this paper constructs a counterexample to prove the sharpness of the error bound $τ$.
Perception Games and Privacy
Venue: arXiv cs.GT 2017
Year: 2017

Players (people, firms, states, etc.) have privacy concerns that may affect their choice of actions in strategic settings. We use a variant of signaling games to model this effect and study its relation to pooling behavior, misrepresentation of information, and inefficiency. We discuss these issues and show that common intuitions may lead to inaccurate conclusions about the implications of privacy concerns.
Strong Duality for a Multiple-Good Monopolist
Venue: arXiv cs.GT 2017
Year: 2017

We characterize optimal mechanisms for the multiple-good monopoly problem and provide a framework to find them. We show that a mechanism is optimal if and only if a measure $μ$ derived from the buyer's type distribution satisfies certain stochastic dominance conditions. This measure expresses the marginal change in the seller's revenue under marginal changes in the rent paid to subsets of buyer types. As a corollary, we characterize the optimality of grand-bundling mechanisms, strengthening several results in the literature, where only sufficient optimality conditions have been derived. As an application, we show that the optimal mechanism for $n$ independent uniform items each supported on $[c,c+1]$ is a grand-bundling mechanism, as long as $c$ is sufficiently large, extending Pavlov's result for $2$ items [Pavlov'11]. At the same time, our characterization also implies that, for all $c$ and for all sufficiently large $n$, the optimal mechanism for $n$ independent uniform items supported on $[c,c+1]$ is not a grand bundling mechanism.
Differentially Private Linear Algebra in the Streaming Model
Venue: arXiv cs.DS 2017
Year: 2017

Numerical linear algebra plays an important role in computer science. In this paper, we initiate the study of performing linear algebraic tasks while preserving privacy when the data is streamed online. Our main focus is the space requirement of the privacy-preserving data-structures. We give the first {\em sketch-based} algorithm for differential privacy. We give optimal, up to logarithmic factor, space data-structures that can compute low rank approximation, linear regression, and matrix multiplication, while preserving differential privacy with better additive error bounds compared to the known results. Notably, we match the best known space bound in the non-private setting by Kane and Nelson (J. ACM, 61(1):4). Our mechanism for differentially private low-rank approximation {\em reuses} the random Gaussian matrix in a specific way to provide a single-pass mechanism. We prove that the resulting distribution also preserve differential privacy. This can be of independent interest. We do not make any assumptions, like singular value separation or normalized row assumption, as made in the earlier works. The mechanisms for matrix multiplication and linear regression can be seen as the private analogues of the known non-private algorithms. All our mechanisms, in the form presented, can also be computed in the distributed setting.
Robust solutions of uncertain mixed-integer linear programs using decomposition techniques
Venue: arXiv cs.NA 2017
Year: 2017

Robust optimization is a framework for modeling optimization problems involving data uncertainty and during the last decades has been an area of active research. If we focus on linear programming (LP) problems with i) uncertain data, ii) binary decisions and iii) hard constraints within an ellipsoidal uncertainty set, this paper provides a different interpretation of their robust counterpart (RC) inspired from decomposition techniques. This new interpretation allows the proposal of an ad-hoc decomposition technique to solve the RC problem with the following advantages: i) it improves tractability, specially for large-scale problems, and ii) it provides the exact probability of constraint violation in case the probability distribution of uncertain parameters are completely defined by using first and second-order probability moments. An attractive aspect of our method is that it decomposes the second-order cone programming problem, associated with the robust counterpart, into a linear master problem and different quadratically constrained problems (QCP) of considerable lower size. The optimal solution is achieved through the solution of these master and subproblems within an iterative scheme based on cutting plane approximations of the second-order cone constraints. In addition, proof of convergence of the iterative method is given.
Maintaining a Distributed Spanning Forest in Highly Dynamic Networks
Venue: arXiv cs.DC 2017
Year: 2017

Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-level graph transformations, which we adapt here in a (synchronous) message passing model for dynamic networks. The resulting algorithm has the following properties: First, every decision is purely local---in each round, a node only considers its role and that of its neighbors in the tree, with no further information propagation (in particular, no wave mechanisms). Second, whatever the rate and scale of the changes, the algorithm guarantees that, by the end of every round, the network is covered by a forest of spanning trees in which 1) no cycle occur, 2) every node belongs to exactly one tree, and 3) every tree contains exactly one root (or token). We primarily focus on the correctness of this algorithm, which is established rigorously. While performance is not the main focus, we suggest new complexity metrics for such problems, and report on preliminary experimentation results validating our algorithm in a practical scenario.
Control Improvisation
Venue: arXiv cs.FL 2017
Year: 2017

We formalize and analyze a new automata-theoretic problem termed control improvisation. Given an automaton, the problem is to produce an improviser, a probabilistic algorithm that randomly generates words in its language, subject to two additional constraints: the satisfaction of an admissibility predicate, and the exhibition of a specified amount of randomness. Control improvisation has multiple applications, including, for example, generating musical improvisations that satisfy rhythmic and melodic constraints, where admissibility is determined by some bounded divergence from a reference melody. We analyze the complexity of the control improvisation problem, giving cases where it is efficiently solvable and cases where it is #P-hard or undecidable. We also show how symbolic techniques based on Boolean satisfiability (SAT) solvers can be used to approximately solve some of the intractable cases.
Multi-Player Diffusion Games on Graph Classes
Venue: arXiv cs.GT 2017
Year: 2017

We study competitive diffusion games on graphs introduced by Alon et al. [1] to model the spread of influence in social networks. Extending results of Roshanbin [8] for two players, we investigate the existence of pure Nash equilibria for at least three players on different classes of graphs including paths, cycles, grid graphs and hypercubes; as a main contribution, we answer an open question proving that there is no Nash equilibrium for three players on (m x n) grids with min(m, n) >= 5. Further, extending results of Etesami and Basar [3] for two players, we prove the existence of pure Nash equilibria for four players on every d-dimensional hypercube.