[Colloquium] JOB TALK: Ryan Williams, IBM on February 7

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, February 7, 2011
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Ryan Williams

From:		IBM Almaden Research Center

Web page:	http://www.cs.cmu.edu/~ryanw/

Title: 		Algorithms, Obstructions, and Beating Exhaustive Search

Abstract:  	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 discuss my work on connecting the art of finding good
algorithms with the art of proving obstructions (a.k.a. lower bounds),
which are impossibility results stating 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 proved. 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 obstructions that had long been conjectured, and
they suggest concrete directions for further progress.

Host: 		Alexander Razborov

Refreshments will be served following the talk at 3:30 in Ryerson 255.