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