Ryan Williams

IBM

Algorithms are the bedrock of computer science. Our algorithmic knowledge is vast, and we apply it everywhere, every day. But while we feel quite knowledgeable about what algorithms can do, we know comparatively little about what algorithms can't do, and have many open conjectures about their weaknesses. The most famous of these conjectures is that P does not equal NP.

 

I will present my work on connecting the art of finding good algorithms with the art of finding obstructions (a.k.a. lower bounds), which are proofs of limitations on what problems can be solved by good algorithms. The connections traverse through a basic question at the heart of P vs NP: for what problems can we avoid exhaustively searching through all possible solutions? Surprisingly, we show that if exhaustive search can be narrowly avoided in some situations, then interesting obstructions can be found in other situations. That is, weak algorithms for solving one problem can be turned into strong obstructions for another problem. These connections have made it possible to prove new complexity lower bounds that had long been conjectured, and they suggest concrete directions for further progress.

 

Bio:

Ryan Williams is a postdoctoral fellow at IBM Almaden Research Center in San Jose, California, supported by the Josef Raviv Memorial Fellowship.  Previously he was a member of the Institute for Advanced Study in Princeton, New Jersey. Ryan received his PhD from Carnegie Mellon in 2007, advised by Manuel Blum, and B.A. and M.Eng. degrees from Cornell. His primary research interests are in the theory of algorithms and computational complexity.

4:15pm

B17 Upson Hall

Tuesday, March 15, 2011

Refreshments at 3:45pm in the Upson 4th Floor Atrium

 

Computer Science

Colloquium

Spring 2011

www.cs.cornell.edu/events/colloquium

Algorithms, Obstructions, and Beating Exhaustive Search