Direct Product Theorems are formal statements of the intuition: "if  
solving one instance of a problem is hard, then solving multiple  
instances is even harder". For example, a Direct Product Theorem with  
respect to bounded size circuits computing a function is a statement  
of the form: "if a function f is hard to compute on average for small  
size circuits, then f^k(x_1, ..., x_k) = f(x_1), ..., f(x_k) is even  
harder on average for certain smaller size circuits". The proof of the  
such a statement is by contradiction: we start with a circuit which  
computes f^k on some non-negligible fraction of the inputs and then  
use this circuit to construct another circuit which computes f on  
almost all inputs. 

As observed by Impagliazzo and Trevisan, such a constructive proof 
yields a decoding  algorithm for the Direct-Product code, where the
 encoding of a message f:{0,1}^n -> {0,1} (viewed as a truth table 
of length 2^n) is the (truth table of) the direct-product function f^k. 
For the parameters of interest (when a received word has only tiny
 agreement with the correct codeword), it is impossible to decode the 
message uniquely, and so one needs to settle for list-decoding, where 
one outputs a list of possible messages. In this case, the list size is the 
main parameter to try to minimize.

We achieve an information-theoretically optimal value of the list size, 
which is a  substantial improvement compared to previous proofs of the
 Direct-Product Theorem. In  particular, this new version can be applied to
 uniform models of  computation (e.g., randomized algorithms) whereas 
all previous  versions applied only to nonuniform models (e.g., circuits).
Moreover, both our new list-decoding algorithm and its analysis are 
extremely simple. Finally, we also get a certain derandomized version of the 
direct-product code.

This is joint work with Russell Impagliazzo, Ragesh Jaiswal, and Avi Wigderson.