The problem of finding large cliques in a graph is a fundamental NP-complete problem with many applications in the sciences. I will examine different approaches to finding cliques as well as some new applications, illustrating some of our work in algorithms and complexity theory in the process. If there is time, I will also discuss some recent work on "applying practice to theory", in which one uses fast problem solvers from practice to attack interesting theoretical problems.
Bio: Ryan Williams is currently a postdoctoral research fellow at Carnegie Mellon University, where he received his PhD in August 2007, advised by Manuel Blum. He received M.Eng. and A.B. degrees from Cornell University. His primary interests are in algorithms and complexity theory, with secondary interests in artificial intelligence and computational notions of privacy. He has received three Best Student Paper awards at major conferences.
Refreshments will be provided at 10:45 AM