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.
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. ... 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 ... 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 ... 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 >>>

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

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 >>>

Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and list error-correction capability. Specifically, for any $\epsilon > 0$, Guruswami and Rudra presented an $n^{O(1/\epsilon)}$ time algorithm to list decode appropriate folded RS codes of rate $R$ from a fraction $1-R-\epsilon$ of ... more >>>

Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal C}$ ... more >>>

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>>

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... more >>>

This paper studies the elementary symmetric polynomials $S_k(x)$ for $x \in \mathbb{R}^n$. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small for some $k>0$ then $|S_\ell(x)|$ is also small for all $\ell > k$. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only $t$-wise ... more >>>

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography ... more >>>

A classical bound in Information Theory asserts that small $L_1$-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on $\{0,1\}^n$ has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>

We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial regime of $m=n^s$, $s>1$, the only known solution, ... more >>>

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is ... more >>>

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the ... more >>>

A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>>

For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{F}^n$ of dimension at most $\eta n$, the image of $U$ under all the maps, $\sum_{j=1}^d ... more >>>

We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability.

This complexity measure gives rise to a ... more >>>

We introduce the notion of pseudo-mixing time of a graph define as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer, where, in addition to the tested vertex, the observer is also provided with oracle access to the ... more >>>

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing ... more >>>

In recent work by Chattopadhyay et al.[CHHL19,CHLT19], the authors exhibit a simple and flexible construction of pseudorandom generators for classes of Boolean functions that satisfy $L_1$ Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG whose seed length depends on ... more >>>

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence:

DistPH is contained in ... more >>>

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this ... more >>>

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},\epsilon)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $\epsilon$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ ... more >>>

The classic Impagliazzo--Nisan--Wigderson (INW) psesudorandom generator (PRG) (STOC `94) for space-bounded computation uses a seed of length $O(\log n \cdot \log(nwd/\varepsilon))$ to fool ordered branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. A series of works have shown that the analysis of the ... more >>>

We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the ... more >>>

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. We show that expander walks fool symmetric functions up to a $O(\lambda)$ error in ... more >>>

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>

A central open problem in complexity theory concerns the question of
whether all efficient randomized algorithms can be simulated by
efficient deterministic algorithms. The celebrated ``hardness
v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84),
Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness
assumptions under which $\prBPP = \prP$, but these hardness ... more >>>

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>

We prove that the sum of $t$ boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of $O(\lambda/t^{1/2-o(1)})$, where $\lambda$ is the second largest eigenvalue of the random walk matrix in absolute value. To ... more >>>

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>