CS Paper Radar

Deterministic Shift Equivalence Testing for Sparse Polynomials

Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal

cs.DS cs.CC ·submitted 2026-10-19 19:04 UTC · v1
top venue

Abstract

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

Comment
To appear in SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Low-Degree Testing Over Boolean Slices

cs.CC ·2026-08-22 ·Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
publishedtheory similarity 0.69
Abstract · 47 pages

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

0.38

Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters

cs.DS math.AC ·2026-09-08 ·Qiao-Long Huang, Xiao-Shan Gao
similarity 0.63
Abstract

Let $A, B \in \mathbb{Z}[x_1, \dots, x_n]$ be multivariate polynomials with integer coefficients and let $G = \gcd(A, B)$. We present an algorithm for computing $G$ whose expected bit complexity is asymptotically linear in all fundamental parameters: the number of variables $n$, the term count $T = \max\{\|A\|_0, \|B\|_0, \|G\|_0\}$, the total degree $D$, and the logarithmic coefficient sizes $\log\Hi$ and $\log\Ho$, where $\Hi$ bounds the coefficients of the inputs and $\Ho$ bounds those of the GCD. The bit complexity is characterized by the clean bound \[ \widetilde{O}\bigl( n \cdot T \cdot D \cdot \log\Hi \cdot \log\Ho \bigr). \] To our knowledge, this is the first sparse GCD algorithm over the integers that achieves linear complexity in all these parameters simultaneously. The integer algorithm is built upon a new field GCD algorithm. For $A, B \in \K[x_1, \dots, x_n]$ over a field $\K$ with $\operatorname{char}(\K) = 0$ or $\operatorname{char}(\K) > °G$, we give the first algorithm that computes $G = \gcd(A,B)$ with expected \[ \widetilde{O}\bigl( n \cdot T \cdot D \bigr) \] field operations, which is both input- and output-sensitive. The key technical contribution behind both algorithms is a derivative-aided separated Hensel lifting technique introduced in this paper. By introducing an auxiliary variable and leveraging derivative information, our scheme extracts all partial exponents via a single $z^2$-lift per variable, achieving constant sequential depth $O(1)$. This stands in sharp contrast to classical Hensel lifting, which requires $O(D)$ sequential lifting steps and suffers from representation densification in the sparse setting. The field algorithm is then extended to the integer case through modular reduction and rational reconstruction.

0.32

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

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

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

cs.CC ·2026-09-29 ·V. Arvind, Pushkar S. Joglekar
publishedtheory similarity 0.60
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

Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

cs.DS ·2026-11-12 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.59
Abstract

We consider a special block-structured integer program with $n$ blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective $c^{\intercal}x + g(Ax)$, where $c$ is a rational cost vector, $A$ is an integral matrix with $d$ rows, and $g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\}$ is an arbitrary function. We access $g$ via an oracle that minimizes $c^{\intercal}x + g(Ax)$ when all but $O(d)$ variables are fixed. Our algorithm runs in time $(ndΔ)^{O(d)}(Q + \text{poly}(|I|))$ where $Δ$ is the largest absolute value of an entry in $A$, $Q$ is the necessary time to evaluate the oracle for $g$ and $|I|$ is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time $t^d(dΔ)^{O(d^2)}Q$ where $t$ is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time $(mΔ)^{O(m)}\text{poly}(|I|)$, where $m$ is the number of constraints involving integral variables and $Δ$ is the largest absolute value of coefficients of integral variables. This improves the dependence on $m$ in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time $w_{\max}^{O(d)}\text{poly}(|I|)$ where $w_{\max}$ is the maximum weight of an item and $d$ the number of different weights.

0.26

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.59
Abstract

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

0.35

Tight Lower Bounds for Algebraic Communication and Applications

cs.CC ·2026-09-15 ·Manon Blanc, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Meena Mahajan
publishedtheory similarity 0.59
Abstract · Strengthened the deterministic Equality lower bound, thereby also proving the Unordered Equality lower bound. Minor improvements to the pres…

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties. In this work, we study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. There are two players, Alice and Bob, with inputs $X\in \mathbb{F}^n$ and $Y\in \mathbb{F}^n$, respectively. In the polynomial evaluation problem, the goal is to compute the value of a polynomial $g\in \mathbb{F}[X,Y]$ on the given input. In the set-recognition problem, the goal is to decide whether $(X,Y)\in S$, for a given set $S\subseteq \mathbb{F}^{n} \times \mathbb{F}^n$. In both settings, Alice and Bob send evaluations of polynomials depending only on their own inputs. In the set-recognition problem, a referee receives the messages and may apply polynomial tests to the messages received so far; the outcomes of these tests determine acceptance or rejection. The protocols may be deterministic or probabilistic. We give non-trivial upper bounds for a range of natural polynomial evaluation and set-recognition problems. We also prove reductions between different problems. Our main technical contribution is a general framework for proving lower bounds for algebraic set-recognition problems. Using this framework, we prove several probabilistic lower bounds for natural problems. In a number of cases, these lower bounds match the corresponding upper bounds, giving tight or near-tight characterizations of their algebraic communication. Finally, we give two applications of our framework. First, we use the communication lower bounds to prove lower bounds for a class of left-to-right algebraic algorithms, which we call algebraic scanners. Second, we show that our lower bound arguments extend beyond polynomials to a more general algebraic computational setting inspired by the Blum--Shub--Smale model.

0.27