Amnon Ta-Shma

We deal with the problem of extracting as much randomness as possible

from a defective random source.

We devise a new tool, a ``merger'', which is a function that accepts

d strings, one of which is uniformly distributed,

and outputs a single string that is guaranteed ...
more >>>

Oded Goldreich, Madhu Sudan

We consider the existence of pairs of probability ensembles which

may be efficiently distinguished given $k$ samples

but cannot be efficiently distinguished given $k'<k$ samples.

It is well known that in any such pair of ensembles it cannot be that

both are efficiently computable

(and that such phenomena ...
more >>>

Salil Vadhan

In this paper, we give explicit constructions of extractors which work for

a source of any min-entropy on strings of length $n$. The first

construction extracts any constant fraction of the min-entropy using

O(log^2 n) additional random bits. The second extracts all the

min-entropy using O(log^3 n) additional random ...
more >>>

Luca Trevisan

We introduce a new approach to construct extractors -- combinatorial

objects akin to expander graphs that have several applications.

Our approach is based on error correcting codes and on the Nisan-Wigderson

pseudorandom generator. An application of our approach yields a

construction that is simple to ...
more >>>

Ran Raz, Omer Reingold, Salil Vadhan

We give explicit constructions of extractors which work for a source of

any min-entropy on strings of length n. These extractors can extract any

constant fraction of the min-entropy using O(log^2 n) additional random

bits, and can extract all the min-entropy using O(log^3 n) additional

random bits. Both of these ...
more >>>

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

We give the first construction of a pseudo-random generator with

optimal seed length that uses (essentially) arbitrary hardness.

It builds on the novel recursive use of the NW-generator in

a previous paper by the same authors, which produced many optimal

generators one of which was pseudo-random. This is achieved ...
more >>>

Tzvika Hartman, Ran Raz

Weak designs were defined by Raz, Reingold and Vadhan (1999) and are

used in constructions of extractors. Roughly speaking, a weak design

is a collection of subsets satisfying some near-disjointness

properties. Constructions of weak designs with certain parameters are

given in [RRV99]. These constructions are explicit in the sense that

more >>>

Omer Reingold, Ronen Shaltiel, Avi Wigderson

On an input probability distribution with some (min-)entropy

an {\em extractor} outputs a distribution with a (near) maximum

entropy rate (namely the uniform distribution).

A natural weakening of this concept is a condenser, whose

output distribution has a higher entropy rate than the

input distribution (without losing

much of ...
more >>>

Omer Reingold, Salil Vadhan, Avi Wigderson

The main contribution of this work is a new type of graph product, which we call the zig-zag

product. Taking a product of a large graph with a small graph, the resulting graph inherits

(roughly) its size from the large one, its degree from the small one, and ...
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 >>>

Zeev Dvir, Ran Raz

Mergers are functions that transform k (possibly dependent)

random sources into a single random source, in a way that ensures

that if one of the input sources has min-entropy rate $\delta$

then the output has min-entropy rate close to $\delta$. Mergers

have proven to be a very useful tool in ...
more >>>

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Optimal dispersers have better dependence on the error than

optimal extractors. In this paper we give explicit disperser

constructions that beat the best possible extractors in some

parameters. Our constructions are not strong, but we show that

having such explicit strong constructions implies a solution

to the Ramsey graph construction ...
more >>>

Zeev Dvir, Amir Shpilka

Joshua Buresh-Oppenheim, Rahul Santhanam

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

Luca Trevisan

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

Shankar Kalyanaraman, Chris Umans

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

Zeev Dvir, Ariel Gabizon, Avi Wigderson

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Ran Raz, Amir Yehudayoff

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}:

1. Noise-resistant. A syntactically multilinear ... more >>>

Anup Rao

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... more >>>

Zeev Dvir

An algebraic source is a random variable distributed

uniformly over the set of common zeros of one or more multivariate

polynomials defined over a finite field $F$. Our main result is

the construction of an explicit deterministic extractor for

algebraic sources over exponentially large prime fields. More

precisely, we give ...
more >>>

Zeev Dvir, Avi Wigderson

A merger is a probabilistic procedure which extracts the

randomness out of any (arbitrarily correlated) set of random

variables, as long as one of them is uniform. Our main result is

an efficient, simple, optimal (to constant factors) merger, which,

for $k$ random vairables on $n$ bits each, uses a ...
more >>>

Matt DeVos, Ariel Gabizon

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ...
more >>>

Zeev Dvir

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a

distribution $X$ on binary strings of length $n$ is a

$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$

to any string of length $n$. For every $\delta>0$ we construct the

following poly($n$)-time ...
more >>>

Eli Ben-Sasson, Noga Ron-Zewi

Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner from affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, ... more >>>

Eli Ben-Sasson, Ariel Gabizon

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>

Bruno Bauwens, Marius Zimand

A $c$-short program for a string $x$ is a description of $x$ of length at most $C(x) + c$, where $C(x)$ is the Kolmogorov complexity of $x$. We show that there exists a randomized algorithm that constructs a list of $n$ elements that contains a $O(\log n)$-short program for $x$. ... more >>>

Gil Cohen

We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of $r$ (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of $r$ random variables ... more >>>

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

Raghu Meka

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... 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 >>>

Gil Cohen

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>

Gil Cohen, Leonard Schulman

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any $\delta > 0$ we construct an extractor for $O(1/\delta)$ $n$-bit sources with min-entropy $(\log{n})^{1+\delta}$. This is most interesting when $\delta$ is set to a small constant, though the result also yields an ... more >>>

Gil Cohen

We construct non-malleable extractors with seed length $d = O(\log{n}+\log^{3}(1/\epsilon))$ for $n$-bit sources with min-entropy $k = \Omega(d)$, where $\epsilon$ is the error guarantee. In particular, the seed length is logarithmic in $n$ for $\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>>

Gil Cohen

A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These ... more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

We explicitly construct extractors for two independent $n$-bit sources of $(\log n)^{1+o(1)}$ min-entropy. Previous constructions required either $\mathrm{polylog}(n)$ min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}.

Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction ... more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

We construct explicit two-source extractors for $n$ bit sources,

requiring $n^\alpha$ min-entropy and having error $2^{-n^\beta}$,

for some constants $0 < \alpha,\beta < 1$. Previously, constructions

for exponentially small error required either min-entropy

$0.49n$ \cite{Bou05} or three sources \cite{Li15}. The construction

combines somewhere-random condensers based on the Incidence

Theorem \cite{Zuc06,Li11}, ...
more >>>

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... 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 >>>

Rohit Agrawal

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions $f:\{0,1\}^m \to \mathbb{R}$ such that $f(U_m)$ has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact ... more >>>

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness.

Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions.

Going from the more restricted model ...
more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in ... more >>>

Eshan Chattopadhyay, Jesse Goodman

An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we ... more >>>

Gil Cohen, Dean Doron, Shahar Samocha

We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions $C$, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\mathrm{Ext}(X,A(Y))$ for every choice of $A \in ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao

We give an explicit construction of an affine extractor (over $\mathbb{F}_2$) that works for affine sources on $n$ bits with min-entropy $k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\mathrm{poly}(\log n)$.

Our construction is ...
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 >>>

Eshan Chattopadhyay, Jyun-Jie Liao

We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits ... more >>>

Eldon Chung, Maciej Obremski, Divesh Aggarwal

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:

(1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.

(2) Constructions where one source is uniform, and the other ...
more >>>

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

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}$. Previously, no constructions were known, even for min-entropy $k\geq n-1$. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of ... more >>>