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

CREATORNikita Gaevoy
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25895

Browse the full library · About the Tower of Babel