Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > LIJIE CHEN:
All reports by Author Lijie Chen:

TR24-182 | 17th November 2024
Lijie Chen, Jiatu Li, Jingxun Liang

Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin

We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice ($AMEXP_{/2^{n^{\varepsilon}}}$) requires circuit complexity at least $2^n/n$. Previously, the best known such near-maximum lower bounds were for symmetric exponential time by Chen, Hirahara, and Ren (STOC'24) and Li (STOC'24), or randomized exponential time with MCSP oracle and ... more >>>




ISSN 1433-8092 | Imprint