OpenRaiser/Intern-Atlas huggingface dataset:
Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design
Venue: arXiv cs.GT 2016
Year: 2016

R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.
Complexity of Nondeterministic Graph Parameter Testing
Venue: arXiv cs.DS 2016
Year: 2016

We study the sample complexity of nondeterministically testable graph parameters and improve existing bounds on it by several orders of magnitude. The technique used would be also of independent interest. We also discuss the special case of weak nondeterministic testing for uniform hypergraphs of arbitrary order.
On the Two-user Multi-carrier Joint Channel Selection and Power Control Game
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a hierarchical game approach to model the energy efficiency maximization problem where transmitters individually choose their channel assignment and power control. We conduct a thorough analysis of the existence, uniqueness and characterization of the Stackelberg equilibrium. Interestingly, we formally show that a spectrum orthogonalization naturally occurs when users decide sequentially about their transmitting carriers and powers, delivering a binary channel assignment. Both analytical and simulation results are provided for assessing and improving the performances in terms of energy efficiency and spectrum utilization between the simultaneous-move game (with synchronous decision makers), the social welfare (in a centralized manner) and the proposed Stackelberg (hierarchical) game. For the first time, we provide tight closed-form bounds on the spectral efficiency of such a model, including correlation across carriers and users. We show that the spectrum orthogonalization capability induced by the proposed hierarchical game model enables the wireless network to achieve the spectral efficiency improvement while still enjoying a high energy efficiency.
AI Evaluation: past, present and future
Venue: arXiv cs.AI 2016
Year: 2016

Artificial intelligence develops techniques and systems whose performance must be evaluated on a regular basis in order to certify and foster progress in the discipline. We will describe and critically assess the different ways AI systems are evaluated. We first focus on the traditional task-oriented evaluation approach. We see that black-box (behavioural evaluation) is becoming more and more common, as AI systems are becoming more complex and unpredictable. We identify three kinds of evaluation: Human discrimination, problem benchmarks and peer confrontation. We describe the limitations of the many evaluation settings and competitions in these three categories and propose several ideas for a more systematic and robust evaluation. We then focus on a less customary (and challenging) ability-oriented evaluation approach, where a system is characterised by its (cognitive) abilities, rather than by the tasks it is designed to solve. We discuss several possibilities: the adaptation of cognitive tests used for humans and animals, the development of tests derived from algorithmic information theory or more general approaches under the perspective of universal psychometrics.
The Advice Complexity of a Class of Hard Online Problems
Venue: arXiv cs.DS 2016
Year: 2016

The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice complexity, we define the first online complexity class, AOC. The class includes independent set, vertex cover, dominating set, and several others as complete problems. AOC-complete problems are hard, since a single wrong answer by the online algorithm can have devastating consequences. For each of these problems, we show that $\log\left(1+(c-1)^{c-1}/c^{c}\right)n=Θ(n/c)$ bits of advice are necessary and sufficient (up to an additive term of $O(\log n)$) to achieve a competitive ratio of $c$. The results are obtained by introducing a new string guessing problem related to those of Emek et al. (TCS 2011) and Böckenhauer et al. (TCS 2014). It turns out that this gives a powerful but easy-to-use method for providing both upper and lower bounds on the advice complexity of an entire class of online problems, the AOC-complete problems. Previous results of Halldórsson et al. (TCS 2002) on online independent set, in a related model, imply that the advice complexity of the problem is $Θ(n/c)$. Our results improve on this by providing an exact formula for the higher-order term. For online disjoint path allocation, Böckenhauer et al. (ISAAC 2009) gave a lower bound of $Ω(n/c)$ and an upper bound of $O((n\log c)/c)$ on the advice complexity. We improve on the upper bound by a factor of $\log c$. For the remaining problems, no bounds on their advice complexity were previously known.
Exploring the Limits of Static Failover Routing
Venue: arXiv cs.NI 2016
Year: 2016

We present and study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph $G$, a unique destination vertex $d$, and an integer constant $c>0$, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source $s$ to the destination $d$ is guaranteed so long as (1) no more than $c$ edges fail and (2) there exists a physical path from $s$ to $d$? We embark upon a systematic exploration of this fundamental question in a variety of models (deterministic routing, randomized routing, with packet-duplication, with packet-header-rewriting) and present both positive and negative results that relate the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions $G$, to its resiliency.
Separate Random Number Generation from Correlated Sources
Venue: arXiv cs.IT 2016
Year: 2016

This work studies the problem of separate random number generation from correlated general sources with side information at the tester under the criterion of statistical distance. Tight one-shot lower and upper performance bounds are obtained using the random-bin approach. A refined analysis is further performed for two important random-bin maps. One is the pure-random-bin map that is uniformly distributed over the set of all maps (with the same domain and codomain). The other is the equal-random-bin map that is uniformly distributed over the set of all surjective maps that induce an equal or quasi-equal partition of the domain. Both of them are proved to have a doubly-exponential concentration of the performance of their sample maps. As an application, an open and transparent lottery scheme, using a random number generator on a public data source, is proposed to solve the social problem of scarce resource allocation. The core of the proposed framework of lottery algorithms is a permutation, a good rateless randomness extractor, whose existence is confirmed by the theoretical performance of equal-random-bin maps. This extractor, together with other important details of the scheme, ensures that the lottery scheme is immune to all kinds of fraud under some reasonable assumptions.
Intermittent Map Matching with the Discrete Fréchet Distance
Venue: arXiv cs.CG 2016
Year: 2016

In this paper we focus on the map matching problem where the goal is to find a path through a planar graph such that the path through the vertices closely matches a given polygonal curve. The map matching problem is usually approached with the Fréchet distance matching the edges of the path as well. Here, we formally define the discrete map matching problem based on the discrete Fréchet distance. We then look at the complexities of some variations of the problem which allow for vertices in the graph to be unique or reused, and whether there is a bound on the length of the path or the number of vertices from the graph used in the path. We prove several of these problems to be NP-complete, and then conclude the paper with some open questions.
A Sample-Based Approach to Data Quality Assessment in Spatial Databases with Application to Mobile Trajectory Nearest-Neighbor Search
Venue: arXiv cs.DB 2016
Year: 2016

Spatial data is playing an emerging role in new technologies such as web and mobile mapping and Geographic Information Systems (GIS). Important decisions in political, social and many other aspects of modern human life are being made using location data. Decision makers in many countries are exploiting spatial databases for collecting information, analyzing them and planning for the future. In fact, not every spatial database is suitable for this type of application. Inaccuracy, imprecision and other deficiencies are present in location data just as any other type of data and may have a negative impact on credibility of any action taken based on unrefined information. So we need a method for evaluating the quality of spatial data and separating usable data from misleading data which leads to weak decisions. On the other hand, spatial databases are usually huge in size and therefore working with this type of data has a negative impact on efficiency. To improve the efficiency of working with spatial big data, we need a method for shrinking the volume of data. Sampling is one of these methods, but its negative effects on the quality of data are inevitable. In this paper we are trying to show and assess this change in quality of spatial data that is a consequence of sampling. We used this approach for evaluating the quality of sampled spatial data related to mobile user trajectories in China which are available in a well-known spatial database. The results show that sample-based control of data quality will increase the query performance significantly, without losing too much accuracy. Based on this results some future improvements are pointed out which will help to process location-based queries faster than before and to make more accurate location-based decisions in limited times.
Colorful linear programming, Nash equilibrium, and pivots
Venue: arXiv cs.DM 2016
Year: 2016

The colorful Carathéodory theorem, proved by Bárány in 1982, states that given d+1 sets of points S_1,...,S_{d+1} in R^d, with each S_i containing 0 in its convex hull, there exists a subset T of the union of the S_i's containing 0 in its convex hull and such that T contains at most one point from each S_i. An intriguing question -- still open -- is whether such a set T, whose existence is ensured, can be found in polynomial time. In 1997, Bárány and Onn defined colorful linear programming as algorithmic questions related to the colorful Carathéodory theorem. The question we just mentioned comes under colorful linear programming. The traditional applications of colorful linear programming lie in discrete geometry. In this paper, we study its relations with other areas, such as game theory, operations research, and combinatorics. Regarding game theory, we prove that computing a Nash equilibrium in a bimatrix game is a colorful linear programming problem. We also formulate an optimization problem for colorful linear programming and show that as for usual linear programming, deciding and optimizing are computationally equivalent. We discuss then a colorful version of Dantzig's diet problem. We also propose a variant of the Bárány algorithm, which is an algorithm computing a set T whose existence is ensured by the colorful Carathéodory theorem. Our algorithm makes a clear connection with the simplex algorithm and we discuss its computational efficiency. Related complexity and combinatorial results are also provided.
Cooperative Local Repair in Distributed Storage
Venue: arXiv cs.IT 2016
Year: 2016

Erasure-correcting codes, that support local repair of codeword symbols, have attracted substantial attention recently for their application in distributed storage systems. This paper investigates a generalization of the usual locally repairable codes. In particular, this paper studies a class of codes with the following property: any small set of codeword symbols can be reconstructed (repaired) from a small number of other symbols. This is referred to as cooperative local repair. The main contribution of this paper is bounds on the trade-off of the minimum distance and the dimension of such codes, as well as explicit constructions of families of codes that enable cooperative local repair. Some other results regarding cooperative local repair are also presented, including an analysis for the well-known Hadamard/Simplex codes.
A Note on Rectangle Covering with Congruent Disks
Venue: arXiv cs.CG 2016
Year: 2016

In this note we prove that, if $S_n$ is the greatest area of a rectangle which can be covered with $n$ unit disks, then $2\leq S_n/n<3 \sqrt{3}/2$, and these are the best constants; moreover, for $Δ(n):=(3\sqrt{3}/2)n-S_n$, we have $0.727384<\liminfΔ(n)/\sqrt{n}<2.121321$ and $0.727384<\limsupΔ(n)/\sqrt{n}<4.165064$.
Improved Algorithms for Distributed Entropy Monitoring
Venue: arXiv cs.DS 2016
Year: 2016

Modern data management systems often need to deal with massive, dynamic and inherently distributed data sources. We collect the data using a distributed network, and at the same time try to maintain a global view of the data at a central coordinator using a minimal amount of communication. Such applications have been captured by the distributed monitoring model which has attracted a lot of attention in recent years. In this paper we investigate the monitoring of the entropy functions, which are very useful in network monitoring applications such as detecting distributed denial-of-service attacks. Our results improve the previous best results by Arackaparambil et al. [2]. Our technical contribution also includes implementing the celebrated AMS sampling method (by Alon et al. [1]) in the distributed monitoring model, which could be of independent interest.
Maximizing Symmetric Submodular Functions
Venue: arXiv cs.DS 2016
Year: 2016

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by current research, unlike similar minimization problems which have been widely studied. In this work, we identify a few submodular maximization problems for which one can get a better approximation for symmetric objectives than the state of the art approximation for general submodular functions. We first consider the problem of maximizing a non-negative symmetric submodular function $f\colon 2^\mathcal{N} \to \mathbb{R}^+$ subject to a down-monotone solvable polytope $\mathcal{P} \subseteq [0, 1]^\mathcal{N}$. For this problem we describe an algorithm producing a fractional solution of value at least $0.432 \cdot f(OPT)$, where $OPT$ is the optimal integral solution. Our second result considers the problem $\max \{f(S) : |S| = k\}$ for a non-negative symmetric submodular function $f\colon 2^\mathcal{N} \to \mathbb{R}^+$. For this problem, we give an approximation ratio that depends on the value $k / |\mathcal{N}|$ and is always at least $0.432$. Our method can also be applied to non-negative non-symmetric submodular functions, in which case it produces $1/e - o(1)$ approximation, improving over the best known result for this problem. For unconstrained maximization of a non-negative symmetric submodular function we describe a deterministic linear-time $1/2$-approximation algorithm. Finally, we give a $[1 - (1 - 1/k)^{k - 1}]$-approximation algorithm for Submodular Welfare with $k$ players having identical non-negative submodular utility functions, and show that this is the best possible approximation ratio for the problem.
A travelling wave approach to a multi-agent system with a path-graph topology
Venue: arXiv cs.SY 2016
Year: 2016

The paper presents a novel approach for the analysis and control of a multi-agent system with non-identical agents and a path-graph topology. With the help of irrational wave transfer functions, the approach describes the interaction among the agents from the `local' perspective and identifies travelling waves in the system. It is shown that different dynamics of the agents creates a virtual boundary that causes a partial reflection of the travelling waves. Undesired effects due to the reflection of the waves, such as amplification/attenuation, long transients or string instability, can be compensated by the feedback controllers introduced in this paper. We show that the controllers achieve asymptotic and even string stability of the system.
A Web Traffic Analysis Attack Using Only Timing Information
Venue: arXiv cs.NI 2016
Year: 2016

We introduce an attack against encrypted web traffic that makes use only of packet timing information on the uplink. This attack is therefore impervious to existing packet padding defences. In addition, unlike existing approaches this timing-only attack does not require knowledge of the start/end of web fetches and so is effective against traffic streams. We demonstrate the effectiveness of the attack against both wired and wireless traffic, achieving mean success rates in excess of 90%. In addition to being of interest in its own right, this timing-only attack serves to highlight deficiencies in existing defences and so to areas where it would be beneficial for VPN designers to focus further attention.
On the Number of RF Chains and Phase Shifters, and Scheduling Design with Hybrid Analog-Digital Beamforming
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers hybrid beamforming (HB) for downlink multiuser massive multiple input multiple output (MIMO) systems with frequency selective channels. For this system, first we determine the required number of radio frequency (RF) chains and phase shifters (PSs) such that the proposed HB achieves the same performance as that of the digital beamforming (DB) which utilizes $N$ (number of transmitter antennas) RF chains. We show that the performance of the DB can be achieved with our HB just by utilizing $r_t$ RF chains and $2r_t(N-r_t + 1)$ PSs, where $r_t \leq N$ is the rank of the combined digital precoder matrices of all sub-carriers. Second, we provide a simple and novel approach to reduce the number of PSs with only a negligible performance degradation. Numerical results reveal that only $20-40$ PSs per RF chain are sufficient for practically relevant parameter settings. Finally, for the scenario where the deployed number of RF chains $(N_a)$ is less than $r_t$, we propose a simple user scheduling algorithm to select the best set of users in each sub-carrier. Simulation results validate theoretical expressions, and demonstrate the superiority of the proposed HB design over the existing HB designs in both flat fading and frequency selective channels.
On the Hardness of Bribery Variants in Voting with CP-Nets
Venue: arXiv cs.GT 2016
Year: 2016

We continue previous work by Mattei et al. (Mattei, N., Pini, M., Rossi, F., Venable, K.: Bribery in voting with CP-nets. Ann. of Math. and Artif. Intell. pp. 1--26 (2013)) in which they study the computational complexity of bribery schemes when voters have conditional preferences that are modeled by CP-nets. For most of the cases they considered, they could show that the bribery problem is solvable in polynomial time. Some cases remained open---we solve two of them and extend the previous results to the case that voters are weighted. Moreover, we consider negative (weighted) bribery in CP-nets, when the briber is not allowed to pay voters to vote for his preferred candidate.
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
Venue: arXiv cs.CC 2016
Year: 2016

We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res which is based on the established proof system QU-resolution. Our main results include an exponential separation of the tree-like and general versions of relaxing QU-res, and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity.
Asymptotic Performance Analysis of a K-Hop Amplify-and-Forward Relay MIMO Channel
Venue: arXiv cs.IT 2016
Year: 2016

The present paper studies the asymptotic performance of multi-hop amplify-and-forward relay multiple-antenna communication channels. Each multi-antenna terminal in the network amplifies the received signal, sent by a source, and retransmits it upstream towards a destination. Achievable ergodic rates under both jointly optimal detection and decoding and practical separate decoding schemes for arbitrary signaling schemes, along with the average bit error rate for various receiver structures are derived in the regime where the number of antennas at each terminal grows large without a bound. To overcome the difficulty of averaging over channel realizations we apply large-system analysis based on the replica method from statistical physics. The validity of the large-system analysis is further verified through Monte Carlo simulations of realistic finite-sized systems.
Nuclear Norm of Higher-Order Tensors
Venue: arXiv cs.CC 2016
Year: 2016

We establish several mathematical and computational properties of the nuclear norm for higher-order tensors. We show that like tensor rank, tensor nuclear norm is dependent on the choice of base field --- the value of the nuclear norm of a real 3-tensor depends on whether we regard it as a real 3-tensor or a complex 3-tensor with real entries. We show that every tensor has a nuclear norm attaining decomposition and every symmetric tensor has a symmetric nuclear norm attaining decomposition. There is a corresponding notion of nuclear rank that, unlike tensor rank, is upper semicontinuous. We establish an analogue of Banach's theorem for tensor spectral norm and Comon's conjecture for tensor rank --- for a symmetric tensor, its symmetric nuclear norm always equals its nuclear norm. We show that computing tensor nuclear norm is NP-hard in several sense. Deciding weak membership in the nuclear norm unit ball of 3-tensors is NP-hard, as is finding an $\varepsilon$-approximation of nuclear norm for 3-tensors. In addition, the problem of computing spectral or nuclear norm of a 4-tensor is NP-hard, even if we restrict the 4-tensor to be bi-Hermitian, bisymmetric, positive semidefinite, nonnegative valued, or all of the above. We discuss some simple polynomial-time approximation bounds. As an aside, we show that the nuclear $(p,q)$-norm of a matrix is NP-hard in general but can be computed in polynomial-time if $p=1$, $q = 1$, or $p=q=2$, with closed-form expressions for the nuclear $(1,q)$- and $(p,1)$-norms.