Title: New Proofs of (New) Direct Product Theorems
Speaker: Russell Impagliazzo, IAS and UC San Diego
Date: Wednesday, December 12, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Direct product theorems are formal statements of the intuition, "It is harder to solve multiple instances of a problem than to solve a single instance." For this talk, the amplification of hardness will be in reducing the probability of success for a feasible algorithm. So a direct product result for circuits might say, "If no small circuit can compute Boolean function f(x) with probability at least 1 − δ for a random x, then no circuit of a slightly smaller size can compute f(x1)...f (xk) with even a small probability of success." Besides average-case complexity, direct product results have been very important in derandomization (making a somewhat hard problem into a "pseudo-random" one) and in cryptography, where the goal is to create problems that are reliably hard for the attacker to solve. They have also had non-obvious applications in other areas of complexity.
I discuss two papers (FOCS 06 and CRYPTO 07) with Ragesh Jaiswal, UCSD, and Valentine Kabanets, SFU. However, the talk will also discuss work-in-progress that is joint with Avi Wigderson and Bruce Kapron.