Symmetric Exponential Time Requires Near-Maximum Circuit Size
- Hanlin Ren, University of Oxford
- Time: 2023-12-26 15:00
- Host: Dr. Kuan Cheng
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
We show that there is a language in S_2E (symmetric exponential time) with circuit complexity at least 2^n/n. In particular, this also implies the same near-maximum circuit lower bounds for the classes Σ_2E∩Π_2E and ZPE^NP. Our proofs relativize. Previously, only "half-exponential" circuit lower bounds for these complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was Δ_3E = E^{Σ_2P} (Miltersen, Vinodchandran, and Watanabe COCOON'99).
Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an NP oracle (FZPP^NP) for the range avoidance problem. This algorithm also implies unconditional pseudodeterministic FZPP^NP constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and K^poly-random strings with nearly optimal parameters.
Based on a joint work with Lijie Chen and Shuichi Hirahara and a subsequent improvement by Zeyong Li.
Biography
Hanlin Ren is a third-year DPhil student at the University of Oxford, advised by Prof. Rahul Santhanam. He is interested in computational complexity theory, and his recent works focused on circuit complexity and pseudorandomness. Prior to that, he was an undergraduate student at Tsinghua University and worked on graph algorithms with Prof. Ran Duan.