Search ACM DL

Search Issue

enter search term and/or author name

**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*={*S*_{1}, ċ , *S*_{t}} be a family of subsets of *E* of size *p*. A subfamily *Ŝ* ⊆ *S* is...

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

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

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

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

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

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

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

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

**Invited Paper Foreword**

Foreword

Article No.: 38

DOI: 10.1145/2989249

**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 *i*th bit of an *n*-bit database replicated among two noncommunicating servers, while not revealing any information about *i* to either server. In...