The Weak Rank Principle: Lower Bounds and Applications
Michal Garlík, Svyatoslav Gryaznov, Hanlin Ren, Iddo Tzameret
Abstract
Given two symbolic matrices X and Y of dimensions m × n and n × m, respectively, the rank principle states that when m = n+1 and A is a scalar matrix of rank n+1, the equation XY = A is unsatisfiable. When m is arbitrarily larger than n and A has rank exceeding n, we obtain the weak rank principle. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP), asserting that m pigeons cannot be injected into n holes, extending its counting argument to an algebraic setting. As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, yet we show that these still yield applications analogous to those of WPHP. In particular, using new generalised types of random restrictions, which may be interesting by themselves, this allows us to resolve a number of open problems in proof complexity, including the construction of proof complexity generators for Polynomial Calculus Resolution over the two-element field (PCRF2), new generators for Sherali–Adams (SA), and hardness results for circuit lower bound statements against PCRF2, as detailed below. Generators for PCRF2. We prove exponential size lower bounds for several encodings—both algebraic and CNF—of the weak rank principle in PCR over F2, where no such bounds are known for the WPHP in the regime with arbitrarily many pigeons. In particular, we obtain 2Ω(n) size lower bounds for both algebraic and standard CNF encodings, including the bamboo-tree encoding, which is the most useful and corresponds to a circuit encoding, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Our bounds hold for every matrix A in XY = A, implying that the rank principle forms a proof complexity generator with nearly quadratic stretch. Using a standard iteration technique we amplify the stretch to 2nΩ(1), meaning we obtain a function generator. This resolves an open problem posed by Alekhnovich et al. (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015) concerning the construction of proof complexity generators with good stretch for PCRF2. Generators for SA. Since in SA even the strong pigeonhole principle is easy, we develop a new size lower-bound technique showing that the weak rank principle, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a new relaxed notion of degree and a new corresponding pseudoexpectation tailored specifically to the rank principle (and incompatible with the pigeonhole principle). Circuit lower bound formulas. We show that PCRF2 does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits such as non-commutative algebraic branching programs. This settles an open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCRF2. Rank principle as an axiom. Finally, we demonstrate the centrality of the weak rank principle by showing that it is necessary for proving NC2 circuit lower bounds and sufficient for proving AC0[p] lower bounds.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Meta-Mathematics of Algebraic Complexity cites Reverse Mathematics of Complexity Lower Bounds
- On Matrix Multiplication and Polynomial Identity Testing cites Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
Cited by top-tier papers1
Builds on4
- Automating algebraic proof systems is NP-hardSusanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi et al.STOC 2021 · 6 citations
- Ideals, determinants, and straightening: proving and using lower bounds for polynomial idealsRobert Andrews, Michael A. ForbesSTOC 2022 · 6 citations
- Reverse Mathematics of Complexity Lower BoundsLijie Chen, Jiatu Li, Igor C. OliveiraFOCS 2024 · 4 citations
- On Matrix Multiplication and Polynomial Identity TestingRobert AndrewsFOCS 2022 · 1 citation
Related papers
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systemsIlario Bonacina, Maria Luisa BonetLICS 2022 · 3 citations
- Lower Bounds for Regular Resolution over ParitiesKlim Efremenko, Michal Garlík, Dmitry ItsyksonSTOC 2024 · 1 citation
- Lower Bounds for Near-Quadratic-Depth Resolution over ParitiesSreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Russell ImpagliazzoSTOC 2026 · 2 citations
- (Semi)Algebraic proofs over ±1 variablesDmitry SokolovSTOC 2020
- On Pigeonhole Principles and Ramsey in TFNPSiddhartha Jain, Jiawei Li, Robert Robere, Zhiyang XunFOCS 2024 · 2 citations
