Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits. Our main results are: \begin{itemize} \item There are explicit $AC^0$ circuits of ... more >>>

We prove that to store n bits x so that each prefix-sum query Sum(i) := sum_{k < i} x_k can be answered by non-adaptively probing q cells of log n bits, one needs memory > n + n/log^{O(q)} n. Our bound matches a recent upper bound of n + n/log^{Omega(q)} ... more >>>

We prove that to store n bits x so that each prefix-sum query Sum(i) := sum_{k < i} x_k can be answered by non-adaptively probing q cells of log n bits, one needs memory > n + n/log^{O(q)} n. Our bound matches a recent upper bound of n + n/log^{Omega(q)} ... more >>>

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

We prove lower bounds on the redundancy necessary to represent a set $S$ of objects using a number of bits close to the information-theoretic minimum $\log_2 |S|$, while answering various queries by probing few bits. Our main results are: \begin{itemize} \item To represent $n$ ternary values $t \in \zot^n$ in ... more >>>

We prove that the sum of $d$ small-bias generators $L : \F^s \to \F^n$ fools degree-$d$ polynomials in $n$ variables over a prime field $\F$, for any fixed degree $d$ and field $\F$, including $\F = \F_2 = {0,1}$. Our result improves on both the work by Bogdanov and Viola ... more >>>

Hardness amplification is the fundamental task of converting a $\delta$-hard function $f : {0,1}^n -> {0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$, where $f$ is $\gamma$-hard if small circuits fail to compute $f$ on at least a $\gamma$ fraction of the inputs. Typically, $\eps,\delta$ are small (and $\delta=2^{-k}$ captures the case ... more >>>

We give a self-contained exposition of selected results in additive combinatorics over the group {0,1}^n. In particular, we prove the celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and the Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result by Samorodnitsky ('07) that linear transformations are efficiently ... more >>>

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$: \begin{enumerate} \item a ... more >>>

In this paper we study the one-way multi-party communication model, in which every party speaks exactly once in its turn. For every fixed $k$, we prove a tight lower bound of $\Omega{n^{1/(k-1)}}$ on the probabilistic communication complexity of pointer jumping in a $k$-layered tree, where the pointers of the $i$-th ... more >>>

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following: (I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following: 1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$. We concentrate on the following two problems: Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$. Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$. ... more >>>

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

We study the complexity of computing $k$-wise independent and $\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$. Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e. given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$. Mansour, Nisan and Tiwari (1990) show that ... more >>>

We revisit the problem of hardness amplification in $\NP$, as recently studied by O'Donnell (STOC `02). We prove that if $\NP$ has a balanced function $f$ such that any circuit of size $s(n)$ fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then $\NP$ has a function $f'$ such ... more >>>

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$ where $C$ is a polynomial-size constant depth circuit and $C$ and the $q$'s are generated from $x$ arbitrarily. We ... more >>>

We study the complexity of building pseudorandom generators (PRGs) from hard functions. We show that, starting from a function f : {0,1}^l -> {0,1} that is mildly hard on average, i.e. every circuit of size 2^Omega(l) fails to compute f on at least a 1/poly(l) fraction of inputs, we can ... more >>>