Search ACM DL

Search Issue

enter search term and/or author name

**The Locality of Distributed Symmetry Breaking**

Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider

Article No.: 20

DOI: 10.1145/2903137

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 article we work in the LOCAL model (where the input graph and...

**Sample Compression Schemes for VC Classes**

Shay Moran, Amir Yehudayoff

Article No.: 21

DOI: 10.1145/2890490

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

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

Dimitris Achlioptas, Fotis Iliopoulos

Article No.: 22

DOI: 10.1145/2818352

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

**On the Complexity of the Orbit Problem**

Ventsislav Chonev, Joël Ouaknine, James Worrell

Article No.: 23

DOI: 10.1145/2857050

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

**Formally Reasoning About Quality**

Shaull Almagor, Udi Boker, Orna Kupferman

Article No.: 24

DOI: 10.1145/2875421

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

**Semantics Out of Context**: Nominal Absolute Denotations for First-Order Logic and Computation

Murdoch J. Gabbay

Article No.: 25

DOI: 10.1145/2700819

Call a semantics for a language with variables *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...

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

Bernhard Haeupler

Article No.: 26

DOI: 10.1145/2629696

We introduce projection analysis—a new technique to analyze the stopping time of protocols that are based on random linear network coding (RLNC). Projection analysis drastically simplifies, extends, and strengthens previous results on RLNC...

**Invited Articles Foreword**

Eva Tardos

Article No.: 27e

DOI: 10.1145/2940319

**Approximation Resistance from Pairwise-Independent Subgroups**

Siu On Chan

Article No.: 27

DOI: 10.1145/2873054

We show optimal (up to a constant factor) NP-hardness for a maximum constraint satisfaction problem with *k* variables per constraint (Max-*k*CSP) whenever *k* is larger than the domain size. This follows from our main result...

**Improved Algorithms for Constructing Consensus Trees**

Jesper Jansson, Chuanqi Shen, Wing-Kin Sung

Article No.: 28

DOI: 10.1145/2925985

A *consensus tree* is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most...