Latest Articles

## Sample Compression Schemes for VC Classes

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size k means that given an arbitrary list of labeled examples, one can retain only k of them in a way that allows us to recover the labels of all other... (more)

## On the Complexity of the Orbit Problem

We consider higher-dimensional versions of Kannan and Lipton’s Orbit Problem—determining whether a target vector space ν may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when ν has dimension one, this... (more)

## Formally Reasoning About Quality

In recent years, there has been a growing need and interest in formally reasoning about the quality of software and hardware systems. As opposed to traditional verification, in which one considers the question of whether a system satisfies a given specification or not, reasoning about quality addresses the question of how well the system satisfies... (more)

## Improved Algorithms for Constructing Consensus Trees

A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many... (more)

##### NEWS

Important Note on P/NP: Some submissions purport to solve a long-standing open problem in complexity theory, such as the P/NP problem. Many of these turn out to be mistaken, and such submissions tax JACM volunteer editors and reviewers. JACM remains open to the possibility of eventual resolution of P/NP and related questions, and continues to welcome submissions on the subject. However, to mitigate the burden of repeated resubmissions due to incremental corrections of errors identified during editorial review, no author may submit more than one such paper to JACM, ACM Trans. on Algorithms, or ACM Trans. on Computation in any 24-month period, except by invitation of the Editor-in-Chief. This applies to resubmissions of previously rejected manuscripts. Please consider this policy before submitting a such a paper.

The Journal of the ACM (JACM) provides coverage of the most significant work on principles of computer science, broadly construed. The scope of research we cover encompasses contributions of lasting value to any area of computer science. To be accepted, a paper must be judged to be truly outstanding in its field.  JACM is interested  in work in core computer science and at the boundaries, both the boundaries of subdisciplines of computer science and the boundaries between computer science and other fields.

##### Forthcoming Articles
Semantics out of context: nominal absolute denotations for logic and computation

Call a semantics for a language with variables \emph{absolute} when variables map to fixed entities in the denotation. That is, a semantics is absolute when the denotation of a variable $a$ is a copy of itself in the denotation. We give a trio of lattice-based, sets-based, and algebraic absolute semantics to first-order logic. Possibly open predicates are directly interpreted as lattice elements / sets / algebra elements, subject to suitable interpretations of the connectives and quantifiers. In particular, universal quantification $\Forall{a}\phi$ is interpreted using a new notion of \emph{fresh-finite'} limit $\freshwedge{a}\model{\phi}$ and using a novel dual to substitution. The interest of this semantics is partly in the non-trivial and beautiful technical details, which also offer certain advantages over existing semantics---but also the fact that such semantics exist at all suggests a new way of looking at variables and the foundations of logic and computation, which may be well-suited to the demands of modern computer science.

#### 63:3 Invited Articles Foreword

How to Delegate Computations: The Power of No-Signaling Proofs

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t=t(n), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is polylog(t), and the running time of the verifier is n*polylog(t). In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE. To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et-al (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

Exponential Separation of Information and Communication for Boolean Functions

We show an exponential gap between communication complexity and information complexity, by giving an explicit example of a partial boolean function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman, our gap is the largest possible. By a result of Braverman and Rao, our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold, answering a long standing open problem. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

The Locality of Distributed Symmetry Breaking

Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this paper we work in the $\LOCAL$ model (where the input graph and underlying distributed network are identical) and study the {\em randomized} complexity of four fundamental symmetry breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes \begin{itemize} \item An MIS algorithm running in $O(\log^2\Delta + 2^{O(\sqrt{\log\log n})})$ time, where $\Delta$ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when $\log n \ll \Delta \ll 2^{\sqrt{\log n}}$, and comes close to the $\Omega(\log \Delta)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. \item A maximal matching algorithm running in $O(\log\Delta + \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $\Delta$ is {\em provably optimal}. \item A $(\Delta+1)$-coloring algorithm requiring $O(\log\Delta + 2^{O(\sqrt{\log\log n})})$ time, improving on an $O(\log\Delta + \sqrt{\log n})$-time algorithm of Schneider and Wattenhofer. \item A method for reducing symmetry breaking problems in low arboricity/degeneracy graphs to low degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an $O(\sqrt{\log n})$-time maximal matching algorithm for graphs with arboricity up to $2^{\sqrt{\log n}}$ and an $O(\log^{2/3} n)$-time MIS algorithm for graphs with arboricity up to $2^{(\log n)^{1/3}}$. \end{itemize} Each of our algorithms is based on a simple, but powerful technique for reducing a {\em randomized} symmetry breaking task to a corresponding {\em deterministic} one on a $\poly(\log n)$-size graph.

Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices

Randomness is a vital resource for modern day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high quality random numbers generated securely. Here we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in the devices, requiring only a unit size quantum memory per device component for the honest implementation, and allowing a large natural class of constructions for the protocol. In conjunct with a recent work by Chung, Shi and Wu, it also leads to robust unbounded expansion using just 2 multi-part devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Renyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements, and a method for simulating trusted measurements with untrusted devices.

#### Constant rate PCPs for CircuitSat with sublinear query complexity

Approximate constraint satisfaction requires large LP relaxations

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.

#### Analyzing Network Coding (Gossip) Made Easy

Optimal Rate Code Constructions for Computationally Simple Channels

We consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently simple circuit. Codes for such channel models are attractive since, like codes for standard adversarial errors, they can handle channels whose true behavior is unknown or varying over time. For two classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only inefficiently decodable codes were previously known. In each case, we provide one en- coder/decoder that works for every channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel. Unique decoding for additive errors: We give the first construction of a polynomial-time encod- able/decodable code for additive (a.k.a. oblivious) channels that achieve the Shannon capacity 1  H(p). These are channels which add an arbitrary error vector e  {0, 1}^N of weight at most pN to the transmitted word; the vector e can depend on the code but not on the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases. List-decoding for polynomial-time channels: For every constant c > 0, we give a Monte Carlo construction of an code with optimal rate (arbitrarily close to 1  H(p)) that efficiently recovers a short list containing the correct message with high probability for channels describable by circuits of size at most N^c. We are not aware of any channel models considered in the information theory literature, other than purely adversarial channels, which require more than linear-size circuits to implement. We justify the relaxation to list-decoding with an impossibility result showing that, in a large range of parameters (p > 1/4), codes that are uniquely decodable for a modest class of channels (online, memoryless, nonuniform channels) cannot have positive rate.

Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms

Let M = (E,I) be a matroid and let S={S_1, ... , S_t} be a family of subsets of E of size p. A subfamily subset of S is q-representative for S if for every set Y subset of E of size at most q, if there is a set X in S disjoint from Y with X \cup Y in I, then there is a set in disjoint from Y with \cup Y in I. By the classical result of Bollobas, in a uniform matroid, every family of sets of size p has a q-representative family with at most (p+q choose p) sets. In his famous two families theorem'' from 1977, Lovasz proved that the same bound also holds for any matroid representable over a field F. As observed by Marx, Lovasz's proof is constructive. In this paper we show how Lovasz's proof can be turned into an algorithm constructing a q-representative family of size at most (p+q choose p) in time bounded by a polynomial in (p+q choose p), t, and the time required for field operations. We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following. - In the LONGEST DIRECTED CYCLE problem the input is a directed n-vertex graph G and the positive integer k. The task is to find a directed cycle of length at least k in G, if such a cycle exists. As a consequence of our 8^{k+o(k)} n^{O(1)} time algorithm, we have that a directed cycle of length at least log(n), if such cycle exists, can be found in polynomial time. - In the MINIMUM EQUIVALENT GRAPH (MEG) problem we are seeking a spanning subdigraph D' of a given n-vertex digraph D with as few arcs as possible in which the reachability relation is the same as in the original digraph D. The existence of a single-exponential c^n-time algorithm for some constant c>1 for MEG was open since the work of Moyles and Thompson [JACM 1969]. - To demonstrate the diversity of applications of the approach, we provide an alternative proof of the recent results recently for algorithms on graphs of bounded treewidth, showing that many connectivity'' problems such as HAMILTONIAN CYCLE or STEINER TREE can be solved in time 2^O(t) * n on n-vertex graphs of treewidth at most t. We believe that expressing graph problems in `matroid language'' shed light on what makes it possible to solve connectivity problems single-exponential time parameterized by treewidth. For the special case of uniform matroids on n elements, we give a faster algorithm computing a representative family. We use this algorithm to provide the fastest known deterministic parameterized algorithms for k-PATH, k-TREE, and more generally, for k-SUBGRAPH ISOMORPHISM, where the k-vertex pattern graph is of constant treewidth.

#### Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected $n$-vertex graph $G$, a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of demand pairs and an integer $c$. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by $c$. When the maximum allowed congestion is $c=1$, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an $O(\sqrt n)$-approximation, by rounding the standard multi-commodity flow relaxation of the problem. This matches the $\Omega(\sqrt n)$ lower bound on the integrality gap of this relaxation. We show an $O(poly\log k)$-approximation algorithm for EDPwC with congestion $c=2$, by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of $\tilde{\Omega}\left((\log n)^{1/(c+1)}\right )$ for any constant congestion $c$. Prior to our work, the best approximation factor for EDPwC with congestion $2$ was $\tilde O(n^{3/7})$, and the best algorithm achieving a polylogarithmic approximation required congestion $14$.

#### Approximation Resistance from Pairwise Independent Subgroups

Are Lock-Free Concurrent Algorithms Practically Wait-Free?

Lock-free concurrent algorithms guarantee that \emph{some} concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were \emph{wait-free}, guaranteeing that \emph{all} operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a \emph{stochastic scheduler}. Our analysis relates the individual performance of processes with the global performance of the system using \emph{Markov chain lifting} between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability $1$, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

Query Complexity of Approximate Nash Equilibria

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n. Our main result states that for n-player binary-action games and for constant µ, the query complexity of an µ-well-supported Nash equilibrium is exponential in n. As a consequences of this result, we get an exponential lower bound on the rate of convergence of adaptive dynamics to approximate Nash equilibria.

Random Walks that Find Perfect Objects and the Lovász Local Lemma

We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lovász Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.