Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers 1 1 1 A preliminary abbreviated version of this work appears in STOC 2024. The preliminary version included a quantitative strengthening of the lower bound against multilinear constant-depth IPS refutations from [ GHT22 ] .

Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret · 2024

Read Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers 1 1 1 A preliminary abbreviated version of this work appears in STOC 2024. The preliminary version included a quantitative strengthening of the lower bound against multilinear constant-depth IPS refutations from [ GHT22 ] . by Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret (2024) 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-2412-20114.txt.

Description

Tuomas Hakoniemi, Nutan Limaye, and Iddo Tzameret study lower bounds for algebraic proofs in a 2024 paper. Strong proof systems can refute false formulas via polynomial ideals. Bounding their size is a core complexity challenge. A functional method reduces proof hardness to circuit hardness.

Symmetry gives the authors a general way to mint hard instances. New hard cases arise over finite fields for proof fragments. Instances beyond subset-sum variants are also obtained. Stronger constant-depth lower bounds follow from the machinery. The paper then exposes a limit of the method itself. It cannot yield lower bounds for hard Boolean instances against strong systems. That barrier result is proved, not just suspected. Proof complexity gains both new weapons and a mapped wall. The work appeared in part at a top theory conference. Specialists in algebraic complexity are the readers.

Catalog record

CREATORTuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE212 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20114

Browse the full library · About the Tower of Babel