All reports by Author Pulkit Sinha:

__
TR24-104
| 12th June 2024
__

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha#### NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials

Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse ... more >>>