Ryan Williams, Massachusetts Institute of Technology

Abstract

Some years ago, I was an REU student at DIMACS, where I met Dieter van Melkebeek and Lance Fortnow. At the time, they had recently proved some time-space tradeoff lower bounds for satisfiability (building on recent work of Lipton and Viglas). I will discuss this topic, some of my own later contributions to it, and its role in inspiring the circuit lower bounds program that currently drives my group's work.

Speaker Bio: Ryan Williams is Associate Professor of Electrical Engineering and Computer Science at MIT. His research is in algorithm design and complexity theory, with a particular emphasis on connections between the two. Williams was an invited speaker in the section on mathematical aspects of computer science at the International Congress of Mathematicians in 2014, a Microsoft Research Faculty Fellow, an Alfred P. Sloan Research Fellow and received a Google Faculty Research award and the NSF CAREER award. Williams was also a participant in the DIMACS Research Experiences for Undergraduates (REU) program in 2000 and was among the first US students to travel to Prague as part of the DIMACS REU partnership with DIMATIA.

Slides  Video