CS Paper Radar

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

Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin

cs.CC ·submitted 2026-11-05 13:05 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Exponential Correlation Bounds for Polynomials

cs.CC ·2026-09-23 ·Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal +1 more
publishedtheoryhighly cited similarity 0.77
Abstract · 26 pages. Revision: Generalized the main results to all fields, added new applications and improved some existing ones, and expanded the exp…

We prove that the XOR of $k$ majorities on disjoint blocks of $\ell$ bits has correlation at most $(4d/\sqrt{\ell})^k$ with every Boolean-valued degree-$d$ polynomial over an arbitrary field. By known techniques, we obtain explicit pseudorandom generators that fool such polynomials on $n$ Boolean inputs with seed length $d^2\cdot\polylog(n/\varepsilon)$. The correlation and the generator extend to small $\mathsf{AC}^0[q]$ circuits, for every fixed prime power $q$. These results resolve several long-standing questions in circuit complexity and pseudorandomness.

0.61

The Complexity of Choosing Parity Projections

cs.CC ·2026-10-30 ·Karthik Sheshadri, Nicholas Smirnov
theory similarity 0.71
Abstract

Cube attacks in cryptanalysis seek small sets of Boolean variables (cubes) whose parity sum is constant. We study the bounded constant derivative problem introduced by Smirnov (2026), which seeks a smallest cube with sum 1, and its sum-0 analogue. Despite their similarity, the problems differ sharply in parameterized complexity: the sum-1 problem admits a $2^{O(k^2)}\operatorname{poly}(N)$-time algorithm, where $k$ is cube size, whereas the sum-0 problem is not fixed-parameter tractable unless $\mathrm{FPT}=\mathrm{W}[1]$. Without a bound on cube size, both problems are $Σ_2^{\oplus\mathrm{P}}$-complete and NP-hard to approximate within $N^{1-\varepsilon}$ for every fixed $0<\varepsilon<1$. Our hardness proofs use a crown construction that embeds maximal monomials of parity-projected circuits into positive 2CNF. This yields completeness and inapproximability results, as well as a dichotomy for Boolean constraint languages of arity at most two: the bounded constant derivative problem is in P when all relations are affine and $Σ_2^{\oplus\mathrm{P}}$-complete otherwise. We also give algorithms parameterized by the number of quadratic rounds, treewidth, or ordered branching-program width, with lower bounds for the first two unless $\mathrm{NP}\subseteq\mathrm{SUBEXP}$. The treewidth lower bound holds for circuits; the case of 2CNF remains open.

0.23

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

cs.CC ·2026-09-29 ·V. Arvind, Pushkar S. Joglekar
publishedtheory similarity 0.70
Abstract

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space. We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE. As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE. The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction. By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC. We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$. Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{Θ(s)}$ yields a polynomial space algorithm.

0.63

Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

cs.CC math.CO ·2026-10-19 ·Xin Li, Yan Zhong
publishedtheory similarity 0.69
Abstract

We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.

0.52

Optimal Shallow Circuits for Majority

cs.CC ·2026-09-27 ·Victor Lecomte, Prasanna Ramakrishnan
theoryhighly cited similarity 0.68
Abstract

Four decades on, Håstad's classical $2^{Ω(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are substantially larger than those for Parity and have repeatedly been conjectured to be optimal. We present a simple construction, found by GPT-6 Astra, of depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for any symmetric function. This result settles the asymptotic $\mathrm{AC}^0$ circuit complexity of Majority, matching Håstad's lower bound. The proof draws inspiration from well-loved combinatorial tools, including the color-coding technique of Alon, Yuster, and Zwick (1995).

0.33

An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division

cs.CC math.AG ·2026-08-26 ·Jizhou Guo
theoryhot direction similarity 0.68
Abstract · 14 pages. Version 2: the passage to valid division is credited to Strassen and Baur-Strassen (version 1 presented it as new); refines the cr…

We record lower bounds for permanent circuits with valid division over characteristic zero, counting nonscalar multiplications and divisions while additions and scalar operations are free. Chapter 5 of OpenAI's Ten Advances supplies the block construction and critical-locus estimate; these, with the parameter choice made here and the classical bounds of Strassen and Baur-Strassen, give liminf as n tends to infinity of L_div(per_n)/(n^2 log_2 log_2 n) >= 1/12. Our finite-parameter refinement for matching-minor polynomials observes that the coefficient vector at deletion size h lies in a space of dimension at most min{binom(t,h), binom(t,d-h)}. Twelve machine-checked declarations of the Lean development accompanying OpenAI's manuscript on border determinantal complexity of the permanent (September 24, 2026) imply, by a short written argument, the existence of a geometric slice; a further written, unformalized application of the same criterion gives L_div(per_n) >= (n^2/119790) log_2(n/44) for n >= 1936. Assuming Proposition 7.3 of that manuscript gives the bound (n^2/86400) log_2(n/48) for n >= 1408. These are order-of-growth results; the elementary Hessian bound n^2/2 is larger at practical orders.

0.39

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.68
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

Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time

cs.CC ·2026-10-27 ·Yichuan Cao, Xiao-Shan Gao, Qiao-Long Huang, Jiawei Nie
theory similarity 0.68
Abstract

In this paper, we prove that irreducibility testing for sparse polynomials in $\mathbb{Z}[X]$ is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless $\mathrm P=\mathrm{NP}$. We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in $\mathsf{PP}\subseteq\mathsf{PSPACE}$; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that $\mathsf{SparseIrred}_{\mathbb{Z}}\in\mathsf{PP}$ relies on the quasi-Riemann hypothesis result of Cureton--Thorner and on the uniform effective prime-ideal bound by Frei--Sofos--Widmer just posted recently.

0.32