Search ACM DL

Search Issue

enter search term and/or author name

**Faster and Simpler Sketches of Valuation Functions**

Keren Cohavi, Shahar Dobzinski

Article No.: 30

DOI: 10.1145/3039871

We present fast algorithms for sketching valuation functions. Let *N* (|*N*| = *n*) be some ground set and *v*:2^{N}→ R be a function. We say that...

**Time vs. Information Tradeoffs for Leader Election in Anonymous Trees**

Christian Glacet, Avery Miller, Andrzej Pelc

Article No.: 31

DOI: 10.1145/3039870

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the *leader*. If the nodes of the network have distinct labels, then agreeing on a single node...

**For-All Sparse Recovery in Near-Optimal Time**

Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

Article No.: 32

DOI: 10.1145/3039872

An *approximate sparse recovery system* in ℓ_{1} norm consists of parameters *k*, ε, *N*; an *m*-by-*N* measurement Φ; and a recovery algorithm *R*. Given a vector, **x**, the system...

**Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution**

David G. Harris, Aravind Srinivasan

Article No.: 33

DOI: 10.1145/3039869

Moser and Tardos have developed a powerful algorithmic approach (henceforth MT) to the Lovász Local Lemma (LLL); the basic operation done in MT and its variants is a search for “bad” events in a current configuration. In the...

**Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform**

Mahdi Cheraghchi, Piotr Indyk

Article No.: 34

DOI: 10.1145/3029050

For every fixed constant α > 0, we design an algorithm for computing the *k*-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an *N*-dimensional vector *x* ∈...

**Uniform Kernelization Complexity of Hitting Forbidden Minors**

Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh

Article No.: 35

DOI: 10.1145/3029051

The *F*-M*F* and an input consisting of a graph *G* and integer *k*, whether *k* vertices can be removed from *G* such that the...

**Representative Families of Product Families**

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

Article No.: 36

DOI: 10.1145/3039243

A subfamily *F′* of a set family *F* is said to *q*-*represent* *F* if for every *A* ∈ *F* and *B* of size *q* such that *A*∩*B* = ∅ there exists a set...