2 papers
cs.CC2025
New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
Lijie Chen, Yang Hu, Hanlin Ren
The *algebrization barrier*, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Not…
cs.CC2023
Symmetric Exponential Time Requires Near-Maximum Circuit Size
Lijie Chen, Shuichi Hirahara, Hanlin Ren
We show that there is a language in (symmetric exponential time with one bit of advice) with circuit complexity at least . In particular, the abo…