CS Peer Talk | Symmetric Exponential Time Requires...

第三十六期

报告人：Hanlin Ren, University of Oxford

时间：12月26日（星期二）3:00pm

地点：静园五院204

报告信息

Title

Symmetric Exponential Time Requires Near-Maximum Circuit Size

Abstract

We show that there is a language in $\mathsf{S}_2\mathsf{E}$ (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 $\sum_2\mathsf{E}\cap\prod_2\mathsf{E}$ and $\mathsf{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_3\mathsf{E}= \mathsf{E}^{\sum_2\mathsf{P}}$ (Miltersen, Vinodchandran, and Watanabe COCOON'99).

Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an $\mathsf{NP}$ oracle ( $\mathsf{FZPP^{NP}}$ ) for the range avoidance problem. This algorithm also implies unconditional pseudodeterministic $\mathsf{FZPP^{NP}}$ constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and $\mathrm{K^\text{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.

about CS Peer Talk

作为活动的发起人，我们来自北京大学图灵班科研活动委员会，主要由图灵班各年级同学组成。我们希望搭建一个CS同学交流的平台，促进同学间的交流合作，帮助同学练习展示，同时增进友谊。

目前在计划中的系列包括但不限于：