Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with local:
TR11-056 | 14th April 2011
Emanuele Viola

Extractors for circuit sources

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

TR13-099 | 6th July 2013
Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Local reductions

Revisions: 3

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

TR17-166 | 3rd November 2017
Emanuele Viola

A sampling lower bound for permutations

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

ISSN 1433-8092 | Imprint