Emanuele Viola

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are:

(1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output ... more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT

instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$

such that there is an explicit circuit $C$ that on input

an index $i$ of $\log |\phi|$ bits outputs the $i$th

clause, and each output bit of $C$ depends on ...
more >>>

Emanuele Viola

A map $f:[n]^{\ell}\to[n]^{n}$ has locality $d$ if each output symbol

in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input

symbols in $[n]$. We show that the output distribution of a $d$-local

map has statistical distance at least $1-2\cdot\exp(-n/\log^{c^{d}}n)$

from a uniform permutation of $[n]$. This seems to be the ...
more >>>