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 err with probability ... more >>>

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 results ... more >>>

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

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 is accepted ... more >>>

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 from ... more >>>

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