Abstract
We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory.
Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any tsparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem.
Formally, for a ring R, let SparseShift_R be the following decision problem  Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results.
1) SparseShift_ℤ is undecidable.
2) For any ring R (which is not a field) such that HN_R is NP_Rcomplete over the BlumShubSmale model of computation, SparseShift_ is also NP_Rcomplete. In particular, SparseShift_ℤ is also NP_ℤcomplete.
We also study the gap version of the SparseShift_R and show the following.
1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^βgapSparseShift_ℤ is also undecidable (where N is the input length).
2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the βgapSparseShift_R problem is NPhard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^dgapSparseShift_R problem is NPhard when given polynomials of degree at most d, in O(nd) many variables, as input.
BibTeX  Entry
@InProceedings{chillara_et_al:LIPIcs.STACS.2023.22,
author = {Chillara, Suryajith and Grichener, Coral and Shpilka, Amir},
title = {{On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {22:122:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17674},
URN = {urn:nbn:de:0030drops176744},
doi = {10.4230/LIPIcs.STACS.2023.22},
annote = {Keywords: algebraic complexity, shift equivalence, polynomial equivalence, Hilbert’s Nullstellensatz, hardness of approximation}
}
Keywords: 

algebraic complexity, shift equivalence, polynomial equivalence, Hilbert’s Nullstellensatz, hardness of approximation 
Collection: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 
Issue Date: 

2023 
Date of publication: 

03.03.2023 