CS Paper Radar

Meta-Mathematics of Algebraic Complexity

Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam, Iddo Tzameret

cs.CC cs.LO ·submitted 2026-10-24 22:48 UTC · v1
top venue

Abstract

We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while algebraic circuit lower bounds are hard for somewhat weak proof systems such as Polynomial Calculus Resolution ($\mathsf{PCR}$), contemporary lower bounds are efficiently provable in proof systems and bounded arithmetic theories corresponding to $\mathsf{NC}^2$, such as $\mathsf{VNC}^2$ and the corresponding class of propositional Frege proofs of quasipolynomial-size. Moreover, going below $\mathsf{VNC}^2$ into algebraic constant-depth reasoning is likely insufficient to efficiently prove already constant-depth algebraic circuit lower bounds. Under an algebraic analogue of the Krajicek--Razborov conjecture, our results suggest that proving superpolynomial lower bounds for general algebraic circuits will require stronger reasoning than that used in the rank-based proofs studied here. Specifically, we show the following.

Comment
A preliminary version of this work appeared in the proceedings of ACM-IEEE LICS 2026
DOI
10.4230/LIPIcs.LICS.2026.49

Closest papers

Nearest neighbours by meaning across the whole index.

The Proof Analysis Problem for Constant-Depth Frege

cs.CC ·2026-11-05 ·Noel Arteche, Susanna F. de Rezende, Erfan Khaniki, Kilian Risse
publishedtheory similarity 0.75
Abstract · An extended abstract of this paper will appear at the 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)

We give a parallel algorithm for the Proof Analysis Problem of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025). The problem asks, given a CNF formula $\varphi$ on $n$ variables and a proof $π$ of a size-$s$ Resolution lower bound on $\varphi$, encoded as $\neg \mathrm{Ref}_s(\varphi)$, to extract a satisfying assignment for $\varphi$ when one exists. The original work gave a polynomial-time extraction algorithm for Resolution refutations that enabled a formalization of the Atserias-Müller lower bound (FOCS 2019) in Extended Frege, but it appeared inherently sequential. We devise a new algorithm that performs assignment extraction in low-depth circuit classes. Specifically, we give an assignment extraction algorithm computable by polynomial-size $\mathbf{TC}^0$ circuits and by quasipolynomial-size $\mathbf{AC}^0$ circuits, and we prove the correctness of the latter within quasipolynomial-size $\mathbf{AC}^0$-Frege. This is thanks to a new formalization of the Atserias-Müller lower bound in the relativized theory $\mathsf{T}^4_2(α)$ of bounded arithmetic, which corresponds to depth-$4$ Frege systems. This yields quasipolynomial-size $\mathbf{AC}^0$-Frege proofs for a broad class of Resolution lower bounds, making progress on a question of Pudlák. A key feature of our approach is an improved parameter regime where we get $\mathbf{AC}^0$-Frege formalizations of Resolution lower bounds $\neg \mathrm{Ref}_s(\varphi)$ for all $s$, including $s = n^{O(1)}$. W also show that the Proof Analysis Problem for $\mathbf{AC}^0$-Frege is $\mathbf{NP}$-hard under quasipolynomial-time reductions, which rules out certain Atserias-Müller-type approaches to the hardness of automating constant-depth Frege. Furthermore, automating $\mathbf{AC}^0$-Frege on Resolution lower bound formulas suffices to automate it on all formulas.

0.32

A Degree--Size Relation for Resolution over Polynomials

cs.CC cs.LO ·2026-09-30 ·Shuo Pang
similarity 0.73
Abstract · Parameters in Section 8 (Conclusions) made explicit

For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operatorname{Res}(\oplus_p)$, separations between different moduli, improved lower bounds for $\operatorname{Res}(k)$ up to $k=\varepsilon\log n$, proof-search consequences, and an implication of super-polynomial $AC^0[p]$-Frege bounds from very strong PC degree lower bounds. The proof uses the common-multiplier idea isolated from Braun [arXiv:2609.23015] to construct a Razborov--Smolensky approximation that preserves inferences, without introducing extension variables. The approximation errors are measured by ranks of the multiplication maps induced by the error-witness polynomials, modulo bounded-degree PC consequences.

0.49

Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy

cs.CC ·2026-10-30 ·Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
theory similarity 0.68
Abstract · Made some minor changes

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its $\mathsf{NP}$-hardness and a $\PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{\mathsf{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $\CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\C[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time. In fact, we show that the reduction holds both ways, and Integral Closure Membership Testing is equivalent to APS under polynomial-time reductions.

0.17

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

cs.CC ·2026-11-05 ·Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
theory similarity 0.67
Abstract

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

0.23

Applicative theories can count

cs.LO ·2026-11-07 ·Melissa Antonelli, Marcel Ertel, Eduardo Skapinakis
hot direction similarity 0.65
Abstract

Applicative theories offer a proof-theoretic framework for studying complexity. In this paper, we introduce a family of applicative theories to characterize classes ranging from constant-depth circuits to polynomial space. Our approach relies on a simple axiom scheme, the small variations of which allows to capture various forms of counting and alternation. This leads to highly uniform results. When applied on notation, the scheme captures bit counting, yielding a characterization of the functions computable by constant-depth, polynomial-size threshold circuits ($\textbf{FTC}^0$); when applied lexicographically, it allows for the counting of accepting computations, yielding a characterization of the functions in the counting hierarchy ($\textbf{FCH}$). Increasing the logical complexity of the induction formulas allowed in the scheme, we obtain characterizations of the functions computable by bounded Boolean circuits of logarithmic-depth and polynomial-size ($\textbf{FNC}^1$) and of the functions computable in polynomial space ($\textbf{FPSPACE}$). The latter characterization solves an open problem in the field. Finally, we investigate separation results. While it is unknown whether $\textbf{FNC}^1$ and $\textbf{FCH}$ are different, there is an oracle relative to which (relativized) $\textbf{FNC}^1$ is strictly contained in (relativized) $\textbf{FCH}$. We use this fact to separate the theories characterizing them, by exploring their ability to represent higher-order functionals.

0.29

A Simple Algebraic Proof of the PCP Theorem

cs.CC ·2026-08-18 ·Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
publishedtheory similarity 0.64
Abstract · Fixed an error in Lemma 3.3 and modified the tests accordingly

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

0.32

Delegating Computation with Approximate Arithmetic: Interactive Proofs for Wizards

cs.CR ·2026-11-08 ·Aritra Das, Debayan Gupta, Arup Mondal, Mihir More
similarity 0.64
Abstract

We study interactive proofs for arithmetic circuits over the complex numbers $\mathbb{C}$ in which both the prover and the verifier compute approximately (unlike muggles, wizards can use magic, i.e., floating-point numbers). The goal is to prove that a claimed output $y$ is close to the exact output $C(x)$: for thresholds $0<Δ_0<Δ$, the honest prover is accepted whenever $|y-C(x)|\leΔ_0$, and every prover is rejected with high probability whenever $|y-C(x)|>Δ$. Existing proof systems for real-valued data verify rounded finite-field computations. Bitan et al.~[EUROCRYPT~2026] gave an approximate sum-check protocol. We extend the protocol of Goldwasser, Kalai, and Rothblum (GKR) [STOC~2008] to public-coin interactive proofs for logspace-uniform layered circuits over $\mathbb{C}$ of size $S$, depth $L$, and $n$ inputs, under public bounds on gate values and wiring coefficients. At constant soundness error, the verifier runs in time $(n+1)\mathrm{poly}(L,\log S,b)$, the communication is $\mathrm{poly}(L,\log S,b)$, and the prover runs in time $\mathrm{poly}(S,b)$, where $b$ is the bit precision. To the best of our knowledge, these are the first doubly efficient interactive proofs in which both parties compute approximately. GKR reduces two claims about a layer to one on a random line, which leaves the unit circle, where our error bounds hold. We instead label gates by complex roots of unity and combine the two claims with a random root of unity as coefficient. We choose the error thresholds backward from the input layer, so that a large output error survives the verifier's rounding at every step. The honest prover needs only $O(S \log S)$ complex operations. We also obtain zero-knowledge proofs from one-way functions, one-round arguments from private information retrieval, and interactive PCPs whose proof length is polynomial in the witness length.

0.36

Ideal Membership in Polynomial Calculus: Complexity and Reductions

cs.CC ·2026-09-23 ·Alex Bortolotti, Monaldo Mastrolilli
theory similarity 0.63
Abstract

The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal <p_1, ..., p_m> of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f from the generators, and a degree-d derivation needs at most n^O(d) steps. We write PC-IMPd for the problem of producing a degree-bounded PC certificate, and call it solvable when one is guaranteed to exist and can be found in time n^O(d). Over Q, unlike over finite fields, a derivation may need exponentially many bits. We study PC-IMPd on instances arising from constraint satisfaction problems, and ask for which constraint languages L it is solvable. Our main contribution is a reduction framework for PC-IMPd, based on pp-definitions, pp-interpretations, and pp-encodings, that mirrors the algebraic approach to CSP complexity. Solvability is preserved by these constructions and, in the language of algebras, by passing to subalgebras, finite direct powers, and homomorphic images. We obtain new tractable classes over ternary and larger domains: every language closed under the median operation on a finite chain has solvable PC-IMPd, by reduction to the Boolean majority algebra, and in particular so does every language over {0, 1, 2} closed under a fixed-value majority. This also places IMPd(L) in P for such languages, advancing the classification of IMPd over ternary domains. In the process, we settle the last open case of the Boolean dichotomy for IMPd(L) and complete the Boolean classification of PC-IMPd(L) with an unconditional lower bound for an instance of PC-IMP1. A recent PC-to-SoS simulation reduces degree-automatability of Sum-of-Squares (the open problem of finding a degree-d SoS proof in time n^O(d) when one exists) to solvability of PC-IMPd. Each new tractable class therefore yields a family of constraint systems on which SoS proofs are degree-automatable.

0.24