Speaker: Hanlin Ren University of Oxford
Time: 2023-12-21 15:30-2023-12-21 16:30
Venue: FIT 1-222

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 \Sigma_2E\cap\Pi_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 \Delta_3E = E^{\Sigma_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.

Short Bio:

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.