Campus Event Calendar

Event Entry

What and Who

The Mystery of the Missing String

Ryan Williams
Stanford University
AG1 Mittagsseminar (own work)

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.
AG 1  
AG Audience

Date, Time and Location

Tuesday, 21 February 2023
60 Minutes
Virtual talk
Virtual talk


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.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

988 5655 4581
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk, but do not have the password, contact Roohani Sharma at

Roohani Sharma, 02/15/2023 17:43
Roohani Sharma, 01/13/2023 18:43
Roohani Sharma, 01/13/2023 18:42 -- Created document.