We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>

When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,
we usually do not specify how to encode instances by binary strings.
This relies on the empirical observation that the truth of a statement of the form ``CIRCUIT-SAT belongs to a complexity class $C$''
more >>>

A circuit $\mathcal{C}$ samples a distribution $\mathbf{X}$ with an error $\epsilon$ if the statistical distance between the output of $\mathcal{C}$ on the uniform input and $\mathbf{X}$ is $\epsilon$. We study the hardness of sampling a uniform distribution over the set of $n$-bit strings of Hamming weight $k$ denoted by $\mathbf{U}^n_k$ ... more >>>

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions as a possible solution to the problem of extracting random keys for cryptographic protocols from weak sources of randomness.
They showed that under a very strong complexity theoretic assumption, there exists a constant $\alpha>0$ such that ... more >>>

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>0$. Recent work by Ball, Goldin, Dachman-Soled and ... more >>>

Trevisan and Vadhan [TV00] first constructed seedless extractors for distributions samplable by poly-size circuits under the very strong complexity theoretic hardness assumption that $E=DTIME(2^{O(n)})$ is hard for exponential size circuits with oracle access to $\Sigma_6^{P}$. Their construction works when the distribution has large min-entropy $k=(1-\gamma) \cdot n$, for small constant ... more >>>

Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from $[n]$. How hard is it to output a sequence in $[n]^n$ that is close to a uniform random permutation? Viola (SICOMP 2020) conjectured that if each output cell is computed by making ... more >>>