Ryan Williams completed his PhD in Computer Science at Carnegie Mellon under Manuel Blum. Following postdocs at the Institute for Advanced Study and IBM Almaden, he was Assistant Professor of Computer Science at Stanford from 2011-2016, and is presently Professor of Electrical Engineering and Computer Science at MIT.
We reconsider the old question of what is the "smallest" complexity class containing a function of high circuit complexity. We show how to view this question and others in terms of a simple problem called Missing String: given a list of m strings of length n, with m<2^n, find a string not on the list. We show in multiple ways how algorithms for Missing String can translate directly into lower bounds, and vice-versa: lower bounds for Missing String can imply upper bounds of a certain form.
Based on a paper with Nikhil Vyas in ITCS'23.