New Circuit Lower Bounds Via Solving Range Avoidance

Almost all n-bit Boolean functions have near-maximum (2^n/n) circuit complexity, and a central challenge of complexity theory is to pinpoint one such hard function. Formally, the goal is to identify the smallest complexity class containing a language with exponential circuit complexity. Despite being extremely important, there had been essentially no progress on this question since the four-decade-old work of Kannan. In particular, it remained open whether Sigma_2 E, an important frontier class in complexity theory, contains a language with exponential circuit complexity.

In a recent paper with Hanlin Ren and Shuichi Hirahara ([CHR'23]), we finally resolved this long-standing open question by showing that Sigma_2 E requires near-maximum (2^n/n) circuit complexity. The lower bound also extends to S_2E/1 (symmetric exponential time with one bit of advice). Our lower bound was further simplified and improved by an exciting recent work by Zeyong Li [Li'23], who showed that S_2E (and therefore Sigma_2 E) requires a maximum circuit complexity on all input lengths.

In this talk, I will explain the new lower bounds for Sigma_2 E, which are corollaries of new algorithms for range avoidance. In particular, I will first describe an algorithm for range avoidance (from [CHR'23]) that works on infinitely many input lengths (which follows the iterative win-win paradigm). I will then explain how [Li'23] significantly simplifies and improves the CHR'23 algorithm to work on all input lengths. This improvement also allows [Li'23] to answer a recent open question posed by Vyas and Williams, giving a quasi-polynomial-size depth-3 AC^0 circuits for the Missing String problem.