TR08-079 Authors: Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

Publication: 9th September 2008 21:18

Downloads: 3266

Keywords:

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} version of the Direct-Product

Theorem with information-theoretically \emph{optimal} parameters, up

to constant factors. Namely, we show that for given $k$ and

$\epsilon$, there is an efficient randomized

algorithm $A$ with the following property. Given a circuit $C$ that

computes $f^k$ on at least $\epsilon$ fraction of inputs, the

algorithm $A$ outputs with probability at least $3/4$ a list of

$O(1/\epsilon)$ circuits such that at least one of the circuits on

the list computes $f$ on more than $1-\delta$ fraction of inputs,

for $\delta = O((\log 1/\epsilon)/k)$; moreover, each output circuit

is an $\AC^0$ circuit (of size $\poly(n,k,\log 1/\delta,1/\epsilon)$),

with oracle access to the circuit $C$.

Using the Goldreich-Levin decoding algorithm~\cite{GL89}, we also

get a \emph{fully uniform} version of Yao's XOR Lemma~\cite{Yao}

with \emph{optimal} parameters, up to constant factors. Our results

simplify and improve those in~\cite{IJK06}.

Our main result may be viewed as an efficient approximate, local,

list-decoding algorithm for direct-product codes (encoding a

function by its values on all $k$-tuples) with optimal

parameters. We generalize it to a family of ``derandomized"

direct-product codes, which we call {\em intersection codes}, where

the encoding provides values of the function only on a subfamily of

$k$-tuples. The quality of the decoding algorithm is then determined

by sampling properties of the sets in this family and their

intersections. As a direct consequence of this generalization we

obtain the first derandomized direct product result in the uniform

setting, allowing hardness amplification with only constant (as

opposed to a factor of $k$) increase in the input length. Finally,

this general setting naturally allows the decoding of concatenated

codes, which further yields nearly optimal derandomized

amplification.