ECCC-Report TR24-104https://eccc.weizmann.ac.il/report/2024/104Comments and Revisions published for TR24-104en-usWed, 12 Jun 2024 10:40:43 +0300
Paper TR24-104
| NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials |
Omkar Baraskar,
Agrim Dewan,
Chandan Saha,
Pulkit Sinha
https://eccc.weizmann.ac.il/report/2024/104An $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.Wed, 12 Jun 2024 10:40:43 +0300https://eccc.weizmann.ac.il/report/2024/104