Abstract
We reconsider the old problem of what is the "smallest" complexity class containing a function of high circuit complexity. We show how to view this problem and other lower bound problems 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. This talk is based on a paper with Nikhil Vyas in ITCS'23.