Speaker: Hanlin Ren, University of Oxford

Time: 15:00 p.m., December 26, 2023, GMT+8

Venue: Room 204, Courtyard No.5, Jingyuan, PKU

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.

Source: Center on Frontiers of Computing Studies, PKU