CS Paper Radar

PIT and Reconstruction for Sums of Powers

Nimrod Kaplan, Amir Shpilka, Yann Tal

cs.CC ·submitted 2026-11-04 20:20 UTC · v1
theory

Abstract

We study deterministic black-box polynomial identity testing (PIT) and reconstruction for polynomials of the form \[ f(x)=\sum_{i=1}^r α_i f_i(x)^d, \] where each $f_i$ belongs to some underlying polynomial class $\mathcal{C}$. This representation generalizes Waring decomposition, several natural small-depth circuit models, and polynomial decompositions arising in moment-based learning problems. Our main results are three lifting theorems showing that, when the outer power is sufficiently large, PIT and reconstruction for the inner class can be lifted to sums of powers. When the power degree is small, we can perform these tasks directly in some of the cases using closure properties of the underlying models. In particular we obtain the following results: \begin{itemize} \item When the inner polynomials have bounded-individual-degrees and are sparse, we obtain deterministic reconstruction for every d: the original power-sum decomposition is recovered at high degree, while at low degree the polynomial is reconstructed nonproperly by sparse interpolation. \item For sums of powers of same-order and any-order read-once oblivious algebraic branching programs, the same proper/nonproper dichotomy gives deterministic reconstruction for every powering degree. \item Explicit quasipolynomial-size hitting sets for every powering degree for several depth-5 and depth-6 circuit families, as well for the models mentioned above. Our results for high powering degree rely on the polynomial ABC theorem, which to the best of our knowledge is the first application of this theorem in the context of PIT.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Depth Hierarchies for Symmetric Algebraic Circuits

cs.CC ·2026-11-17 ·Anuj Dawar, Prateek Dwivedi, Benedikt Pago, Tim Seppelt
similarity 0.59
Abstract · submitted to STOC 2027

Algebraic complexity studies the cost of computing families of polynomials by algebraic circuits, with the central goal of proving super-polynomial circuit lower bounds and separations between different models of algebraic computation. Since such lower bounds remain elusive for general circuits, a common strategy is to focus on restricted models. A recent line of work (ICALP 2020, ITCS & STOC 2026) introduces and studies symmetry as a syntactic circuit restriction, showing exponential symmetric lower bounds for the permanent, as well as separations between symmetric analogues of algebraic formulas ($\mathsf{VF}$), skew circuits ($\mathsf{VS}$), and circuits ($\mathsf{VP}$). We investigate the role of depth as a complexity parameter in symmetric circuits. For every fixed $Δ\geq 1$, we exhibit a family of polynomials computable by symmetric circuits of polynomial size and depth $2Δ+3$, but requiring size $n^{Ω(\log n)}$ at depth $Δ$. We also define symmetric versions of the bounded-depth algebraic complexity classes $\mathsf{VAC}^k$, for all $k \in \mathbb{N}$, that we call $\mathsf{symVAC}^k$, and establish two strict hierarchies: Firstly, a hierarchy within $\mathsf{symVAC}^0$, and secondly, a hierarchy of the form $\mathsf{symVAC}^k \subsetneq \mathsf{symVAC}^{k+1}$ for all $k$. The latter shows that symmetric circuits of depth $(\log n)^{k+1}$ are strictly more powerful than depth-$(\log n)^k$ circuits. Moreover, we place the bounded-depth classes within the landscape of symmetric algebraic complexity developed by Dwivedi, Pago and Seppelt (STOC 2026). We complement this picture by introducing $\mathsf{symVNP}$, a symmetric analogue of $\mathsf{VNP}$, and establishing $\mathsf{symVNP}$-completeness of the permanent under symmetric projections.

0.29

A Separation Between Distribution-Free SQ Learning and Dimension Complexity

cs.CC ·2026-09-17 ·Shyamal Patel
hot direction similarity 0.59
Abstract

We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $Φ_1, \dots, Φ_r$ such that for all $f \in$ C we can write $f(x) = \text{sign} \left( \sum_{i = 1}^r w_i Φ_i(x) \right)$ for some set of weights $w_i \in \mathbb{R}$, we must have that $r \geq n^{ω(1)}$. This gives a superpolynomial separation between dimension complexity and the query complexity of distribution-free learning in the statistical query model, negatively answering a question of Feldman, Kamath, and Srebro [FKS26]. Our construction C is a subclass of DNFs, and the proof is a simple consequence of recent progress on agnostically learning conjunctions [DKR25,CPS26] and the work of Razborov and Sherstov on the sign rank of DNFs [RS10].

0.28

Near-Quadratic Sample Compression for All VC Classes

cs.LG cs.AIcs.DSmath.CO+1 ·2026-11-18 ·Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta +4 more
theory similarity 0.58
Abstract

The sample compression conjecture is a longstanding open problem in learning theory, originating in the work of Littlestone and Warmuth in the 1980s. At its heart is a connection between simplification and generalization: if a predictor consistent with a training sample is defined using only a small part of that sample, then it is likely to generalize. Sample compression schemes formalize this idea, and many natural learning algorithms can be analyzed this way. The sample compression conjecture of Floyd and Warmuth (1995) asserts that every binary concept class of VC dimension $d$ admits a sample compression scheme of size $O(d)$; a weaker conjecture asks only for size polynomial in $d$. Both have remained open: the first bound depending only on $d$, due to Moran and Yehudayoff (2016), is exponential in $d$. We prove the weaker conjecture by constructing a sample compression scheme of size $O(d^2 \log^2 d)$.

0.12

Learning Depth-3 Circuits with Polynomial Savings

cs.DS cs.CC ·2026-09-16 ·Xi Chen, Animesh Fatehpuria, Shyamal Patel, Rocco Servedio
similarity 0.58
Abstract

We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning. Prior algorithms for this problem, due to Servedio and Tan [ST17], could only learn polynomial-size depth-three circuits of poly$(n)$ size over $\{0,1\}^n$ with a running time of $2^{n - Ω(n/\log n)}$, and hence they ran in time $N^{1-o(1)}$ where $N=2^n$ is the running time of a naive memorization-based approach. In this work we substantially improve on the [ST17] result: for any constant $γ\geq1$, we give an algorithm that learns depth-three circuits of size $n^γ$ with running time \[ 2^{n-c_γn}, \] where $c_γ>0$ depends only on $γ$ and not on $n$. Hence we achieve a polynomial savings over the naive approach for learning any polynomial-size depth-three circuit. The main driving force behind our improvement is an improved bound on the approximate degree of width-$k$ CNFs. Inspired by Szegedy [Sze04] and Magniez et al. [MNRS11], the rough idea of our construction is to use a Chebyshev polynomial to efficiently amplify the spectral gap of a carefully designed random walk. This is combined with a random-restriction-like approach to separately learn different subfunctions corresponding to different assignments to a randomly chosen set of variables, using the Perceptron algorithm over a specially designed feature space. A simplified warmup instantiation of our approach achieves $c_γ= \exp(-O(γ))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_γ=Ω(1)/γ$.

0.20

The Complexity of Choosing Parity Projections

cs.CC ·2026-10-30 ·Karthik Sheshadri, Nicholas Smirnov
theory similarity 0.58
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

Deterministic Shift Equivalence Testing for Sparse Polynomials

cs.DS cs.CC ·2026-10-19 ·Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal
top venue similarity 0.57
Abstract · To appear in SODA 2027

We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a vector $\mathbf{a}\in\mathbb{Q}^n$ such that $f(\mathbf{x}+\mathbf{a})\equiv g(\mathbf{x})$. Furthermore, one needs to output such a vector if it exists. Dvir, Oliveira, and Shpilka (ICALP 2014) studied shift equivalence for low-degree arithmetic circuits. Their framew ork does not apply directly to sparse polynomials, which are not closed under shifts, and they left open whether shift equivalence of sparse polynomials admits an efficient deterministic algorithm. We answer this question positively over $\mathbb{Q}$. If the input coefficients have bit-size at most $τ$, we sh ow that a rational shift of polynomial bit-size exists whenever the polynomials are shift equivalent. Moreover, our alg orithm outputs such a shift and has a running time of $\operatorname{poly}(n,s,t,τ,\log d)$ in the bit model. The ar ithmetic and structural parts of our result also hold over any field of characteristic zero or characteristic larger th an $d$.

0.37

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

cs.CC quant-phcs.DS ·2026-10-13 ·Zekun Ye
theory similarity 0.57
Abstract

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity $Θ(nk)$ by combining known sparse-recovery and lower-bound results.

0.05