On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

Suryajith Chillara, Coral Grichener, Amir Shpilka

We say that two given polynomials $f,g\in R[X]$, over a ring $R$, are equivalent under shifts if there exists a vector $a\in R^n$ such that $f(X+a)=g(X)$. Grigoriev and Karpin…