Revision #3 Authors: Pranav Bisht, Ilya Volkovich

Accepted on: 14th July 2022 18:23

Downloads: 22

Keywords:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log n)}$ terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. $s^{poly(d)}$). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give an efficient (deterministic) identity testing algorithms for $\Sigma^{[2]}\Pi\Sigma\Pi^{[\text{ind-deg} \; d]}$ circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.

Abstract updated.

Revision #2 Authors: Pranav Bisht, Ilya Volkovich

Accepted on: 14th July 2022 18:20

Downloads: 5

Keywords:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log n)}$ terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. $s^{poly(d)}$). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give an efficient (deterministic) identity testing algorithms for $\Sigma^{[2]}\Pi\Sigma\Pi^{[\mathsf{ind\text{-}deg} \; d]}$ circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.

Abstract updated.

Revision #1 Authors: Pranav Bisht, Ilya Volkovich

Accepted on: 14th July 2022 18:16

Downloads: 7

Keywords:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log n)}$ terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. $s^{poly(d)}$). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give an efficient (deterministic) identity testing algorithms for $\Sigma^{[2]}\Pi\Sigma\Pi^{[\deg_{x_i} \leq d]}$ circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.

TR22-070 Authors: Pranav Bisht, Ilya Volkovich

Publication: 9th May 2022 07:31

Downloads: 213

Keywords:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log n)}$ terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. $s^{poly(d)}$). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give an efficient (deterministic) identity testing algorithms for $\Sigma^{[2]}\Pi\Sigma\Pi^{[\deg_{x_i} \leq d]}$ circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.