CS Paper Radar

Low-Degree Testing Over Boolean Slices

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard

cs.CC ·submitted 2026-08-22 02:23 UTC · v1
publishedtheory

Abstract

We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2}\to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group, the low-degree testing problem asks us to distinguish the case where $f$ is a polynomial of degree at most $d$ (with coefficients from $G$) or is $\varepsilon$-far from the set of all such polynomials. Classical works in this area considered functions with domain $\mathbb{F}_q^n$ and range $\mathbb{F}_q$. More recent works have considered the setting where the domain is the Boolean cube [Bafna, Srinivasan, Sudan (Random Struct. Algorithms 2020), Amireddy, Srinivasan, Sudan (RANDOM 2023)], or when the domain is the slice (i.e., $\{0,1\}^n_{k}$) and the range is $\mathbb{F}_2$ [David, Dinur, Goldenberg, Kindler and Shinkar (SIAM J. Comput. 2017), Kalai, Lifshitz, Minzer and Ziegler (FOCS 2024)]. Each of the changes introduces new challenges in designing and analyzing low-degree tests and this happens again in our setting with domain being a slice and range is general. Our main theorem gives a test that makes $O_d(1)$ queries to $f$ and accepts degree-$d$ functions while rejecting functions that are $\varepsilon$-far with probability $Ω(\varepsilon)$. The central proof idea is to reduce this low-degree testing problem to the problem of low-degree testing on the cube. Specifically we show how to randomly embed the $n/2$-dimensional cube $\{0,1\}^{n/2}$ in the $n$-dimensional slice while nearly preserving the proximity of $f$ to the space of degree-$d$ polynomials on this cube. While the embedding is simple and natural, the analysis involves a careful induction with a novel use of a basis of degree-$d$ polynomials on slices (from a work of Anstee, Rónyai and Sali (Graphs and Combinatorics 2002)).

Comment
47 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

On Non-Deterministic Representation of Boolean Functions

cs.CC ·2026-11-09 ·Sudharshan Rajagopalan, Nitin Saurabh
publishedtheory similarity 0.65
Abstract · 15 pages, to appear in FSTTCS 2026

We study non-deterministic representation of Boolean functions by polynomials, introduced by (de Wolf, 2000). A polynomial $p(x)$ is said to be a non-deterministic polynomial for a Boolean function $f$ if for all $a\in\{0,1\}^n$, $p(a)\neq 0$ iff $f(a)=1$. The non-deterministic degree of $f$, denoted $\mathsf{ndeg}(f)$, is the minimal degree of a non-deterministic polynomial for $f$. In this work, we show the following main results: - Almost all Boolean functions on $n$ variables have non-deterministic degree at most $n/2 + O(\sqrt{n\log n})$. This confirms a conjecture of (Iyer et al., 2023). Together with the lower bound of (Iyer et al., 2023) it establishes a tight bound on the rational degree of a random Boolean function up to lower order terms. - We disprove a conjecture of (Kothari et al., 2026) about effective hypercube nullstellensatz for more than two polynomials. On the positive side, we also identify a constraint under which an effective hypercube nullstellensatz holds for many polynomials.

0.22

A General Composition Theorem for Approximate Degree

cs.CC quant-ph ·2026-09-24 ·Samruddhi Pednekar, Supartha Podder
theoryhot direction similarity 0.64
Abstract · Added a counterexample to multiplicative composition for exact quantum query complexity

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

0.50

Almost every Boolean function has central threshold degree

cs.DM cs.ITmath.CO ·2026-10-10 ·Martin Anthony
theory similarity 0.64
Abstract · 12 pages. Revised abstract and exposition to clarify the conjectures resolved; references updated. Results and proofs unchanged

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree either $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$, except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. The paper proves a 1991 conjecture of Aspnes, Beigel, Furst and Rudich. It also proves a 1991 conjecture of Wang and Williams for even $n$ and its main concentration assertion for odd $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

0.36

Logarithmic asymptotics for polynomial threshold functions

cs.DM cs.ITmath.CO ·2026-10-25 ·Martin Anthony
theory similarity 0.64
Abstract · 39 pages. Revised exposition and organisation, with expanded explanations. Main results and theorem statements unchanged

We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.

0.12

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

cs.CC math.COcs.DM ·2026-10-12 ·Yuan Li, Jing Zhang
theory similarity 0.63
Abstract · Version 2, 44 pages

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality $s(f)=n$ established in our earlier work yields $bs(f)=C(f)=n$. For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree $d\ge4$. Writing $n=q(d+2)+ρ$, where $0\leρ<d+2$ and $q\ge\max\{2,d/2-1\}$, we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including $C(F_{6,8q+5})=bs(F_{6,8q+5})=8q+2$ for $q\ge2$. Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

0.43

Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

cs.DM math.CO ·2026-09-20 ·Yuan Li, Jing Zhang
theoryhot direction similarity 0.63
Abstract · 26 pages

Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of $σ_{n,d}$ for every $1\le d\le n$. Using Lucas' theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s(σ_{n,d})$, $\bs(σ_{n,d})$, and $C(σ_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(σ_{n,d})<\bs(σ_{n,d})<C(σ_{n,d}), \] and exhibit infinite families for which it holds.

0.48