Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNDECIDABILITY:
Reports tagged with Undecidability:
TR22-106 | 21st July 2022
Suryajith Chillara, Coral Grichener, Amir Shpilka

On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

We say that two given polynomials $f, g \in R[x_1, \ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, \ldots, a_n)\in R^n$ such that $f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>>




ISSN 1433-8092 | Imprint