The Power of Small Symmetries
Nikita Gaevoy · 2026
Read The Power of Small Symmetries by Nikita Gaevoy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25895.txt.
Description
Nikita Gaevoy works in proof complexity, the study of how long a formal proof must be, on a system called Resolution with symmetries. Resolution is a basic proof method for logic formulas, and symmetry rules let a proof reuse a mirrored step for free. Earlier versions allowed symmetries of any size, which is powerful but unrealistic, since finding huge symmetries is computationally out of reach.
Gaevoy defines small symmetries, which may only rearrange a limited number of variables at once, and studies the resulting proof systems. Both the local and global variants form strict hierarchies as the allowed size grows, with exponential separations between levels. Even the lowest levels beat plain Resolution and stronger systems such as constant-depth Frege by an exponential margin. A side result separates the classical systems SRC-I and SR-II exponentially for the first time.
Catalog record
| CREATOR | Nikita Gaevoy |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25895