The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)). This basic construct underlies “hardness amplification” in cryptography, circuit complexity and PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent result by Dinur and ... more >>>

The classical Direct-Product Theorem for circuits says that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard to compute on average by small circuits, then the corresponding $k$-wise direct product function $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each $x_i\in\{0,1\}^n$) is significantly harder to compute on average by slightly smaller circuits. We prove a \emph{fully uniform} ... more >>>

For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can efficiently construct (using \emph{arithmetization}) a low-degree polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all points in the Boolean cube $\{0,1\}^n$; the constructed polynomial $p$ can be interpreted as a polynomial over an arbitrary field $\mathbb{F}$. The problem $\#SAT$ (of counting the number ... more >>>

We consider the problem of amplifying uniform average-case hardness of languages in $\NP$, where hardness is with respect to $\BPP$ algorithms. We introduce the notion of \emph{monotone} error-correcting codes, and show that hardness amplification for $\NP$ is essentially equivalent to constructing efficiently \emph{locally} encodable and \emph{locally} list-decodable monotone codes. The ... more >>>

We prove a version of the derandomized Direct Product Lemma for deterministic space-bounded algorithms. Suppose a Boolean function $g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$ fraction of inputs by any deterministic time $T$ and space $S$ algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step walks $w=(v_1,\dots, v_t)$ ... more >>>

We show that derandomizing Polynomial Identity Testing is, essentially, equivalent to proving circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or, even, nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either ... more >>>

This survey focuses on the recent (after 1998) developments in the area of derandomization, with the emphasis on the derandomization of time-bounded randomized complexity classes. more >>>

We consider a class, denoted APP, of real-valued functions f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to within any epsilon>0, by a probabilistic Turing machine running in time poly(n,1/epsilon). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete ... more >>>

We study the complexity of the circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s. We argue why this problem is unlikely to be in P (or even ... more >>>

Andreev et al.~\cite{ABCR97} give constructions of Boolean functions (computable by polynomial-size circuits) that require large read-once branching program (1-b.p.'s): a function in P that requires 1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a function in LINSPACE ... more >>>