Oded Goldreich

We consider the problem of estimating the average of a huge set of values.

That is,

given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,

we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$

upto an additive error of $\epsilon$.

We are allowed to employ a randomized algorithm which may ...
more >>>

Mihir Bellare, Oded Goldreich, Erez Petrank

A Uniform Generation procedure for $NP$ is an

algorithm which given any input in a fixed NP-language, outputs a uniformly

distributed NP-witness for membership of the input in the language.

We present a Uniform Generation procedure for $NP$ that runs in probabilistic

polynomial-time with an NP-oracle. This improves upon ...
more >>>

H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

We introduce "resource-bounded betting games", and propose

a generalization of Lutz's resource-bounded measure in which the choice

of next string to bet on is fully adaptive. Lutz's martingales are

equivalent to betting games constrained to bet on strings in lexicographic

order. We show that if strong pseudo-random number generators exist,

more >>>

Marius Zimand

We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT ...
more >>>

Ziv Bar-Yossef

We present a novel technique, based on the Jensen-Shannon divergence

from information theory, to prove lower bounds on the query complexity

of sampling algorithms that approximate functions over arbitrary

domain and range. Unlike previous methods, our technique does not

use a reduction from a binary decision problem, but rather ...
more >>>

Oded Goldreich, Or Sheffet

We initiate a general study of the randomness complexity of

property testing, aimed at reducing the randomness complexity of

testers without (significantly) increasing their query complexity.

One concrete motovation for this study is provided by the

observation that the product of the randomness and query complexity

of a tester determine ...
more >>>

Scott Aaronson, Alex Arkhipov

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a

model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ...
more >>>

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

Chris Beck, Russell Impagliazzo, Shachar Lovett

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

Emanuele Viola

We obtain the first deterministic randomness extractors

for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$

generated (or sampled) by single-tape Turing machines

running in time $n^{2-16 \alpha}$, for all sufficiently

small $\alpha > 0$. We also show that such machines

cannot sample a uniform $n$-bit input to the Inner

Product function ...
more >>>

Emanuele Viola

This note proves the existence of a quadratic GF(2) map

$p : \{0,1\}^n \to \{0,1\}$ such that no constant-depth circuit

of size $\poly(n)$ can sample the distribution $(u,p(u))$

for uniform $u$.

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

Huacheng Yu, Wei Zhan

Given a distribution over $[n]^n$ such that any $k$ coordinates need $k/\log^{O(1)}n$ bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality $\Omega(\log(n/k)/\log\log(n/k))$. In particular, we show that for any constant $\delta>0$, there exists $\varepsilon=2^{-\Omega(n^{1-\delta})}$ such that $\Omega(\log n/\log\log n)$ non-adaptive ... more >>>

Daniel Kane, Anthony Ostuni, Kewen Wu

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of ... more >>>