2 papers
cs.CC2026
The Weak Rank Principle: Lower Bounds and Applications
Michal Garl\'\ik, Svyatoslav Gryaznov, Hanlin Ren +1
Given two symbolic matrices and of dimensions and , the *weak rank principle* (WRank) states the equation is unsatisfiable when and ra…
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…