Ryan Williams, CSE Faculty Candidate

Dr. Williams is a Raviv Fellow at the IBM Almaden Research Center in San Jose, CA
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.