Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
by Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson
Oded's comments
What is striking in this version of the Direct Product Theorem
is that it does not require samples of (input,value) pairs
for the basic function (denoted $f$).
Instead, the reduction
(of strongly approximating $f$ to weakly approximating $f^k$)
uses the oracle to generate such samples.
Actually, the reduction makes a single query and based
on it produces, with small probability,
an oracle machine that strongly approximates $f$
(when given oracle access to a weak approximator of $f^k$).
Specifically, for $k'=k/2$, the reduction selects uniformly
a $k'$-subset $A$ of the domain, and generates a machine $M_{A,V}$,
where $V$ is the value obtained from the oracle when querying it on
a random $k$-set that contains $A$.
On input $x$ and oracle access to $F$ (which weakly approximates $f^k$),
the machine $C_{A,V}$ samples random $k$-sets $B$
that contain $A$ and $x$, and returns $F(B)_x$ for the first $V$
that satisfies $F(B)_A=V$. There is also a derandomized version,
which I did not study yet (shame on me!).
The original abstract
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.
Back to
list of Oded's choices.