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   Info

AG Audience

English

60 Minutes

Saarbrücken

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

Zoom

988 5655 4581

passcode not visible

logged in users only

If you wish to attend the talk, but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.