All reports by Author David Zuckerman:

__
TR22-103
| 15th July 2022
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 2

__
TR21-106
| 22nd July 2021
__

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman#### The Space Complexity of Sampling

Revisions: 1

__
TR20-055
| 22nd April 2020
__

Ashutosh Kumar, Raghu Meka, David Zuckerman#### Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

__
TR20-026
| 25th February 2020
__

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman#### Spectral Sparsification via Bounded-Independence Sampling

Revisions: 1

__
TR19-145
| 31st October 2019
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman#### XOR Lemmas for Resilient Functions Against Polynomials

__
TR19-099
| 29th July 2019
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

__
TR19-029
| 20th February 2019
__

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman#### Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

__
TR18-116
| 18th June 2018
__

Xue Chen, David Zuckerman#### Existence of Simple Extractors

Revisions: 1

__
TR18-110
| 4th June 2018
__

Fu Li, David Zuckerman#### Improved Extractors for Recognizable and Algebraic Sources

Revisions: 1

__
TR18-063
| 5th April 2018
__

William Hoza, David Zuckerman#### Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

Revisions: 1

__
TR15-151
| 14th September 2015
__

Eshan Chattopadhyay, David Zuckerman#### New Extractors for Interleaved Sources

Revisions: 1

__
TR15-119
| 23rd July 2015
__

Eshan Chattopadhyay, David Zuckerman#### Explicit Two-Source Extractors and Resilient Functions

Revisions: 5

__
TR14-147
| 6th November 2014
__

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman#### Rectangles Are Nonnegative Juntas

Revisions: 1

__
TR14-102
| 4th August 2014
__

Eshan Chattopadhyay, David Zuckerman#### Non-Malleable Codes Against Constant Split-State Tampering

__
TR13-143
| 19th October 2013
__

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman#### Robust Pseudorandom Generators

Revisions: 1

__
TR13-057
| 5th April 2013
__

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

__
TR12-057
| 7th May 2012
__

Russell Impagliazzo, Raghu Meka, David Zuckerman#### Pseudorandomness from Shrinkage

Revisions: 2

__
TR10-176
| 15th November 2010
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman#### Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

__
TR10-006
| 11th January 2010
__

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan#### Fooling functions of halfspaces under product distributions

Revisions: 2

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR06-026
| 27th February 2006
__

Ronen Gradwohl, Salil Vadhan, David Zuckerman#### Random Selection with an Adversarial Majority

__
TR05-100
| 30th August 2005
__

David Zuckerman#### Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

__
TR05-012
| 17th January 2005
__

Luca Trevisan, Salil Vadhan, David Zuckerman#### Compression of Samplable Sources

__
TR01-036
| 2nd May 2001
__

Amnon Ta-Shma, David Zuckerman, Shmuel Safra#### Extractors from Reed-Muller Codes

__
TR97-045
| 29th September 1997
__

Oded Goldreich, David Zuckerman#### Another proof that BPP subseteq PH (and more).

Comments: 1

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising ... more >>>

Ashutosh Kumar, Raghu Meka, David Zuckerman

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>

Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $F_2$. We introduce a new technique to prove such correlation bounds with $F_2$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

Xue Chen, David Zuckerman

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>>

Fu Li, David Zuckerman

We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources.

Our first method shows that ...
more >>>

William Hoza, David Zuckerman

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

Eshan Chattopadhyay, David Zuckerman

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,

explicit extractors for $2$-interleaved sources on $\{ ...
more >>>

Eshan Chattopadhyay, David Zuckerman

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ... more >>>

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ ... more >>>

Eshan Chattopadhyay, David Zuckerman

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman

Let $G:\{0,1\}^n\to\{0,1\}^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is $(k,q)$-robust if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ ... more >>>

Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

Russell Impagliazzo, Raghu Meka, David Zuckerman

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our ... more >>>

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Ronen Gradwohl, Salil Vadhan, David Zuckerman

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

David Zuckerman

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>

Luca Trevisan, Salil Vadhan, David Zuckerman

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

Oded Goldreich, David Zuckerman

We provide another proof of the Sipser--Lautemann Theorem

by which $BPP\subseteq MA$ ($\subseteq PH$).

The current proof is based on strong

results regarding the amplification of $BPP$, due to Zuckerman.

Given these results, the current proof is even simpler than previous ones.

Furthermore, extending the proof leads ...
more >>>