Metraipolis › archive › dc_4239d86b3f79
The Weak Rank Principle: Lower Bounds and Applications — arXiv:2608.08760
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08760
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:18:32.309Z
- SHA-256 of the archived text
b4029a3c8fd17198b4ea240b1f82bd8719749cab7113edb5cb16a2017946631a- Stable URL of this page
https://metraipolis.com/documento/dc_4239d86b3f79
How to cite
The Weak Rank Principle: Lower Bounds and Applications — arXiv:2608.08760 — arXiv (en), https://arxiv.org/abs/2608.08760 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4239d86b3f79 (Metraipolis archive dc_4239d86b3f79, sha256 b4029a3c8fd17198b4ea240b1f82bd8719749cab7113edb5cb16a2017946631a)
BibTeX
@misc{dc4239d86b3f79,
title = {The Weak Rank Principle: Lower Bounds and Applications — arXiv:2608.08760},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08760},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4239d86b3f79; sha256 b4029a3c8fd17198b4ea240b1f82bd8719749cab7113edb5cb16a2017946631a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08760. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, the *weak rank principle* (WRank) states the equation $XY = A$ is unsatisfiable when $m>n$ and rank of $A$ exceeds $n$. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP). As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications. *Generators for PCR$_{F_2}$*: We prove exponential size lower bounds for algebraic, perfect matching, and bamboo-tree encodings of WRank in PCR$_{F_2}$. The latter encoding is the most relevant for applications to circuit lower-bound formulas, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Using a standard iteration technique we amplify the stretch to exponential. This resolves the open problem concerning the construction of proof complexity generators with good stretch for PCR$_{F_2}$. *Generators for Sherali--Adams:* We develop a new size lower-bound technique showing that WRank, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a pseudoexpectation tailored specifically to the rank principle (and incompatible with WPHP). *Circuit lower bound formulas:* We show that PCR$_{F_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{F_2}$. *Strength of the weak rank principle:* Finally, we show that WRank is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.08760 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:14:58.108Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).