We provide an exposition of three Lemmas which relate
general properties of distributions
with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,
relates the statistical distance of a distribution from uniform
to the maximum bias of the xor of certain bit positions.
The ... more >>>

We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. This ... more >>>

We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family ... more >>>

\begin{abstract}
A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator
(PRFG) if communicating
with a randomly chosen secret function from $F$ cannot be
efficiently distinguished from communicating with a truly random function.
We ask for the minimal hardware complexity of a PRFG. This question ... more >>>

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>

We consider the function ensembles emerging from the
construction of Goldreich, Goldwasser and Micali (GGM),
when applied to an arbitrary pseudoramdon generator.
We show that, in general, such functions
fail to yield correlation intractable ensembles.
Specifically, it may happen that, given a description of such a function,
more >>>

We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good distance.
more >>>

We present an explicit construction of codes that can be list decoded
from a fraction $(1-\eps)$ of errors in sub-exponential time and which
have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal
rate of $\Omega(\eps)$, and is the first sub-exponential complexity
construction to beat the rate of $O(\eps^2)$ achieved by ... more >>>

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science,
probabilistic algorithms are sometimes simpler and more efficient
than the best known ... more >>>

A number of recent results have constructed randomness extractors
and pseudorandom generators (PRGs) directly from certain
error-correcting codes. The underlying construction in these
results amounts to picking a random index into the codeword and
outputting $m$ consecutive symbols (the codeword is obtained from
the weak random source in the case ... more >>>

We study multiplayer games in which the participants have access to
only limited randomness. This constrains both the algorithms used to
compute equilibria (they should use little or no randomness) as well
as the mixed strategies that the participants are capable of playing
(these should be sparse). We frame algorithmic ... more >>>

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>

A theorem of Green, Tao, and Ziegler can be stated (roughly)
as follows: if R is a pseudorandom set, and D is a dense subset of R,
then D may
be modeled by a set M that is dense in the entire domain such that D and
more >>>

A small-biased distribution of bit sequences is defined as one withstanding $GF(2)$-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, $GF(2^n)$ for $n$ that divides the length of the bit sequence. Indeed, this means that we partition the bits ... more >>>

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>

In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>