Computational complexity theory studies the power and limitations of efficient computation. Perhaps the most striking theme of modern complexity theory is the fact that basic notions gain new meanings when computational constraints are taken into consideration. Prominent examples of such notions include proofs, secrecy, knowledge, strategy, communication, interaction, learning---and more recently, even privacy and fairness. Each of these notions predates computer science by millennia, and at first blush, are not intrinsically related to computation. And yet, they have all gained entirely new dimensions, and even spawned entirely new fields, when viewed through the lens of complexity theory. This proposal is centered around another such notion, randomness. Randomized algorithms pervade both the theory and practice of computer science; beyond computer science, randomness is an especially enigmatic phenomenon that has long fascinated and frustrated philosophers, physicists, and mathematicians alike.
The focus of this project is on the complexity-theoretic study of randomness, with a focus on unconditional derandomization, i.e., using concrete constructions to eliminate the need for randomness in certain algorithms. (Famous conjectures, such as P=BPP, posit that randomization can be dispensed with entirely. However, all but a few significant results in this direction make use of unproved assumptions.) This is essentially a fine-grained study of randomness in computing, focusing on simple and natural function classes such as small-width branching programs, various restricted types of circuits and formulas, half-spaces and their generalizations. While these function classes do not capture all polynomial-time computation, results in this area are among the few that can be proved without unproved hypotheses. Furthermore, each of these classes illuminates an important aspect of efficient computation: small-depth circuits capture highly parallelizable computation, small-width branching programs capture memory-efficient computation, half-spaces capture linearly-separable data, and so on. The investigator will develop new structural results for three touchstone function classes in complexity theory---polynomial threshold functions, polytopes, and Boolean formulas in conjunctive normal form---and leverage these results in the design of optimal pseudorandom generators for them.
Research on this project will be fully integrated with a detailed education plan that will involve and help develop graduate and undergraduate students. In addition to advising Ph.D. students, the investigator will continue advise undergraduates through CURIS, Stanford's popular summer undergraduate research internship program; he will develop a comprehensive, year-long course sequence in complexity theory; he will organize an annual young complexity theorists workshop, to be hosted at Stanford; and finally, he plans to publish his lecture notes as a book.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
