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


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.


Refreshments will be offered starting 15 minutes prior to the scheduled start of the talk.

How to Subscribe