Reproduce “Meta-Mathematics of Algebraic Complexity” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
The authors study which proof systems can establish algebraic circuit lower bounds, formalizing rank-based Permanent lower bounds in VNC² and showing they have polynomial-size NC²-Frege proofs. They also prove unconditional PCR proof-size hardness for specified circuit-existence statements. Constant-depth IPS hardness is conditional on tensor-rank hardness, while implications for general rank methods remain conditional on a conjecture.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.