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…