- New Circuit Lower Bounds vi...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in December 2023

## New Circuit Lower Bounds via Solving Range Avoidance

**Speaker:**
Lijie Chen
, UC Berkeley

**Date:**
Thursday, December 07, 2023

**Time:**
4:00 PM to 5:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
32-G575

**Event Type:**
Seminar

**Room Description:**
32-G575

**Host:**
Noah Golowich, MIT

**Contact:**
Noah Golowich, nzg@csail.mit.edu

**Relevant URL:**

**Speaker URL:**
https://chen-lijie.github.io/

**Speaker Photo:**

None

**Reminders to:**
theory-seminars@csail.mit.edu, seminars@csail.mit.edu

**Reminder Subject:**
TALK: Lijie Chen: New Circuit Lower Bounds via Solving Range Avoidance

Abstract:

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.

**Research Areas:**

Algorithms & Theory

**Impact Areas:**

Created by Noah Golowich at Wednesday, December 06, 2023 at 1:28 AM.