Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-104 | 12th June 2024 07:37

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials


Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha
Publication: 12th June 2024 10:40
Downloads: 117


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 asks to check if there exist $A \in \mathrm{GL}(|\mathbf{x}|, \mathbb{F})$ and $\mathbf{b} \in \mathbb{F}^{|\mathbf{x}|}$ such that $f(A\mathbf{x} + \mathbf{b})$ is $s$-sparse. We show that ETsparse is NP-hard over any field $\mathbb{F}$, if $f$ is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-$3$ arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest $s_0$ such that a given $s$-sparse polynomial $f$ is in the orbit of some $s_0$-sparse polynomial to within a factor of $s^{\frac{1}{3} - \epsilon}$ is NP-hard for any $\epsilon >0$; observe that $s$-factor approximation is trivial as the input is $s$-sparse. Finally, we show that for any constant $\sigma \geq 6$, checking if a polynomial (given in sparse representation) is in the orbit of some support-$\sigma$ polynomial is NP-hard. Support of a polynomial $f$ is the maximum number of variables present in any monomial of $f$. These results are obtained via direct reductions from the $\mathrm{3\text{-}SAT}$ problem.

ISSN 1433-8092 | Imprint