Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 13 Issue 3, March 2017

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:2N→ 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-Minor-Free Deletion problem asks, for a fixed set 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 AF and B of size q such that AB = ∅ there exists a set...