Title:  Varieties and applications of direct product theorems 

Speaker: Russell Impagliazzo, UCSD & IAS 
 
Abstract: 

Joint work with Yevginy Dodis, Ragesh Jaiswal, Valentine Kabanets
and Avi Wigderson.

In many areas of complexity theory, we want to make a {\em somewhat} hard
problem into a {\em reliably} hard problem.  An immediate
motivation for this type of {\em hardness amplification } comes
from cryptography and security.
For example, CAPTCHAs are now
widely used to distinguish human users from artificially intelligent
``bots''.
However, current CAPTCHAs are neither impossible for a bot to solve some
significant fraction of the time, nor reliably solved by human users. Can
we make a CAPTCHA both reliably hard for bots and reliably easy for
humans?

The main tools for hardness amplification are {\em direct product
theorems},
where we show that a feasible solver's probability
of solving many instances of a problem
is significantly smaller than their probability of solving a single
instance.  In other words, if $f(x)$ is hard for a constant
fraction of $x$'s, $f^{k}(x_1,..x_k) = f(x_1) \circ f(x_2)..\circ f(x_k)$
is hard on almost every tuple $x_1,...x_k$.
While intuitive, direct product theorems are not always true
and do not
not always have the intuitive parameters even if true.

In this talk, we will give an overview of the many varieties of
direct product theorems from complexity, such as xor lemma,
thresholded direct product theorem, derandomized direct product
theorem, uniform direct product theorems, and direct product testing. We
will sketch why these
different varieties are needed to address a wide range of issues
in complexity theory, such as:  cryptography, average-case complexity,
derandomization, error-correcting codes, and probabilistically
checkable proofs.

We will then show that there are {\em direct reductions} between
three of the different varieties: the xor lemma, standard direct
product and thresholded direct product. (This builds on recent
work of Unger).  These reductions can
also be interpretted combinatorially, and gives
new, more combinatorial, proofs of many known concentration
results, such as Chernoff bounds, Azuma's Lemma, Chernoff
bounds for expander walks, and generalizations.
We give quantitative bounds on how well such reductions
can preserve the adversary's advantage.


If time permits, we will also briefly survey the use of
direct product {\em testing} in probabilistically checkable
proofs.  In direct product testing, the goal is to determine,
given very few oracle calls to a function $F$, whether
there exists a function $f$ whose direct product $f^k$ is close
to $F$.   Direct product testing, introduced by
Goldreich and Safra,  was motivated by the problem
of boosting the soundness of a probabilistically checkable proof.
The parallel repetition of a PCP has queries that are tuples
of queries in the original, and gets a label that is supposed
to be the tuple of labels.
Raz (later improved by Holenstein and Rao) showed that parallel
repetition does increase soundness exponentially, but not at
the rate one might expect intuitively.
Intuitively, adding direct product testing to the parallel
repetition enforces consistency between the answers of the
prover,  not allowing them to change the supposed label of $x_i$
based on the other queries made, which might lead to optimal
improvements in soundness.

Goldreich and Safra's direct product test, later improved
by Dinur and Reingold,  worked only when
there was high correlation between $f^k$ and $F$.  In contrast,
Dinur and Goldenberg give a 2-query  direct product test
when the correlation is $1/k^{\alpha}$ for a constant $\alpha >0$
and show that no 2-query test is possible below correlation
$1/k2$.   In contrast, we give a 3-query test for an exponentially small
correlation.  Somewhat paradoxically, we also use the
same techniques to design 2 query PCP's with exponentially
small soundness.  We also give derandomized direct product tests,
which were subsequently used by Dinur and Meir to give fixed polynomial
size PCP's with subconstant soundness.
We will give just an intuitive overview of these results.