Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 63 Issue 4, November 2016

Section: Parameterized and Exact Algorithms

Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
Article No.: 29
DOI: 10.1145/2886094

Let M=(E, I) be a matroid and let S={S1, ċ , St} be a family of subsets of E of size p. A subfamily ŜS is...

Section: Economics and Computation

Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
Shaddin Dughmi, Tim Roughgarden, Qiqi Yan
Article No.: 30
DOI: 10.1145/2908735

We design the first truthful-in-expectation, constant-factor approximation mechanisms for NP-hard cases of the welfare maximization problem in combinatorial auctions with nonidentical items and in combinatorial public projects. Our results...

Section: Distributed Computing

Are Lock-Free Concurrent Algorithms Practically Wait-Free?
Dan Alistarh, Keren Censor-Hillel, Nir Shavit
Article No.: 31
DOI: 10.1145/2903136

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make...

Section: Probabilistic Proofs

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth
Article No.: 32
DOI: 10.1145/2901294

The PCP theorem [Arora et al. 1998; Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A...

Section: Quantum Information

Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices
Carl A. Miller, Yaoyun Shi
Article No.: 33
DOI: 10.1145/2885493

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...

Section: Complexity Theory

Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Article No.: 34
DOI: 10.1145/2811255

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 no more powerful than...

Section: Coding Theory

Optimal Rate Code Constructions for Computationally Simple Channels
Venkatesan Guruswami, Adam Smith
Article No.: 35
DOI: 10.1145/2936015

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 that adds the...

Section: Economics and Computation

Query Complexity of Approximate Nash Equilibria
Yakov Babichenko
Article No.: 36
DOI: 10.1145/2908734

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...

Section: Constraint Satisfaction & Computational Complexity

The Complexity of Finite-Valued CSPs
Johan Thapper, Stanislav Živný
Article No.: 37
DOI: 10.1145/2974019

We study the computational complexity of exact minimization of rational-valued discrete functions. Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The...

Section: Invited Article

Invited Paper Foreword
Article No.: 38
DOI: 10.1145/2989249

Section: Communication Complexity

2-Server PIR with Subpolynomial Communication
Zeev Dvir, Sivakanth Gopi
Article No.: 39
DOI: 10.1145/2968443

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two noncommunicating servers, while not revealing any information about i to either server. In...