This proposal describes research and educational work in computational complexity, in the three areas of average-case complexity, derandomization and inapproximability. Derandomization is the task of simulating probabilistic algorithms with comparably efficient deterministic ones; Inapproximability is the study of the complexity of finding approximate solutions to combinatorial optimization problems; and averagecase complexity is the area of complexity theory that studies algorithms that work well on most, but not necessarily all, inputs.
These three strongly connected areas are rich in technically deep results and in important open questions. Several new techniques and insights have been developed in the last few years, suggesting the tractability of long-standing open questions as well as the importance of new questions. A wider dissemination of these recent insights, techniques and conjectures is also important.
Intellectual Merits. The research will focus on a number of fundamental questions in each area, as well as on connections between the areas. Here we mention a few of the problems that the PI and his students will work on. On the topic the derandomization, the PI will work on a generalization of Reingold's recent breakthrough derandomization of the random walk algorithm for undirected connectivity. The PI is engaged in ongoing work with Dinur, Reingold and Vadhan to generalize the result to arbitrary randomized log-space algorithms. On average-case complexity, the PI will work on the question: can cryptography be based on NPhardness? Work by Ajtai, Dwork, Micciancio Regev and others on lattice-based cryptosystems gives hope for a positive answer, while recent work by the PI and Bogdanov gives a parital negative answer. This proposal describes work towards a general negative resolution of the question. At the intersetion between average-case complexity and inapproximability, the PI will study the complexity of certifying unsatisfiability of random k-SAT istances and the inapproximability results that can be proved assuming the intractability of this problem. On the topic of inapproximability results based on probabilistically checkable proofs (PCPs), the PI will work towards constructing "two-to-one" PCPs, a weakening of the "Unique Games" conjectured by Khot, and then use such PCPs to prove inapproximability results without resorting to the unproved Unique Games Conjecture.
Broader Impact. This proposal supports two graduate students, who will work with the PI on the problems described here, and present their results at international conferences. Three graduate courses at Berkeley will be influenced by this grant. An extensive survey paper on average-case complexity will be written next year, and another survey paper is planned for the following year. Several of the questions addressed in this proposal are fundamental, and methods devised for their resolution are likely to lead to other discoveries in unrelated fields. The question of basing cryptography on the weakest possible assumptions is of broad interest in computer science and beyond.
