enter search term and/or author name
Faster and Simpler Sketches of Valuation Functions
Keren Cohavi, Shahar Dobzinski
Article No.: 30
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
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
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
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
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
Representative Families of Product Families
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
Article No.: 36
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...