In a recent breakthrough [1], Chattopadhyay and Zuckerman gave an explicit two-source
extractor for min-entropy k≥ log C n for some large enough constant C, where n is the …

In the long-studied problem of combinatorial group testing, one is asked to detect a set of k
defective items out of a population of size n, using m≪ n disjunctive measurements. In the …

The group testing problem consists of determining a small set of defective items from a
larger set of items based on tests on groups of items, and is relevant in applications such as …

We establish several “sharp threshold” results for computational complexity. For certain
tasks, we can prove a resource lower bound of nc for c≥ 1 (or obtain an efficient circuit …

Abstract The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and
the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) …

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 approximates x …

In this paper, a deterministic sparse Fourier transform algorithm is presented which breaks
the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting …

Many applications of machine learning on discrete domains, such as learning preference
functions in recommender systems or auctions, can be reduced to estimating a set function …

We consider the problem of computing the Walsh-Hadamard Transform (WHT) of some $ N
$-length input vector in the presence of noise, where the $ N $-point Walsh spectrum is $ K …

In this paper, we consider the extensively studied problem of computing a k-sparse
approximation to the d-dimensional Fourier transform of a length n signal. Our algorithm …