Colloquium Details
Barriers in Cryptography and Complexity Theory
Speaker: Boaz Barak, Assistant Professor of Computer Science, Princeton University
Location: Warren Weaver Hall 1302
Date: February 23, 2009, 11:30 a.m.
Host: Michael Overton
Synopsis:
What techniques will eventually resolve major questions of computer science, such as P vs NP, designing secure cryptosystems, or the explicit construction of pseudorandom objects?
Theoretical Computer Science is perhaps uniquely "self-referential" in its rigorous attempts to understand the power of natural families of techniques to solve such major questions. A number of "barrier results" are known, showing that certain goals are *impossible* to achieve by natural families of techniques (i.e., the ones commonly used to achieve important special cases of these goals). In this overview talk I will survey two important examples of such barriers: the "black-box" barrier in cryptography, and the "natural proofs" barrier in the area of explicit constructions of combinatorial objects.
I will discuss the longstanding goals these barrier results apply to, as well as works that bypass these barriers in certain contexts, with some applications. These include cryptographic protocols for asynchronous networks, and the construction of Ramsey graphs. I will also describe recent works that attempt to "pit the two barriers against each other", using insights from combinatorial constructions as a source of hard problems to attack longstanding cryptographic goals.
The talk will be self-contained and will not assume any background in cryptography or complexity theory.
Notes:
In-person attendance only available to those with active NYU ID cards.