Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #6 to TR22-070 | 25th October 2022 19:28

#### On Solving Sparse Polynomial Factorization Related Problems

Revision #6
Authors: Pranav Bisht, Ilya Volkovich
Accepted on: 25th October 2022 19:28
Downloads: 59
Keywords:

Abstract:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor 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 efficient (deterministic) algorithms for identity testing of $\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.

Changes to previous version:

Previous version had the incorrect (old) pdf

Revision #5 to TR22-070 | 25th October 2022 19:17

#### On Solving Sparse Polynomial Factorization Related Problems

Revision #5
Authors: Pranav Bisht, Ilya Volkovich
Accepted on: 25th October 2022 19:17
Downloads: 17
Keywords:

Abstract:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor 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 efficient (deterministic) algorithms for identity testing of $\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.

Changes to previous version:

Abstract typesetting corrected.

Revision #4 to TR22-070 | 1st October 2022 01:28

#### On Solving Sparse Polynomial Factorization Related Problems

Revision #4
Authors: Pranav Bisht, Ilya Volkovich
Accepted on: 1st October 2022 01:28
Downloads: 23
Keywords:

Abstract:

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor 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 efficient (deterministic) algorithms for identity testing of $\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.

Changes to previous version:

Updated reviewer comments

Revision #3 to TR22-070 | 14th July 2022 18:23

#### On Solving Sparse Polynomial Factorization Related Problems

Revision #3
Authors: Pranav Bisht, Ilya Volkovich
Accepted on: 14th July 2022 18:23
Downloads: 101
Keywords:

Abstract:

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.

Changes to previous version:

Abstract updated.

Revision #2 to TR22-070 | 14th July 2022 18:20

#### On Solving Sparse Polynomial Factorization Related Problems

Revision #2
Authors: Pranav Bisht, Ilya Volkovich
Accepted on: 14th July 2022 18:20
Downloads: 32
Keywords:

Abstract:

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.

Changes to previous version:

Abstract updated.

Revision #1 to TR22-070 | 14th July 2022 18:16

#### On Solving Sparse Polynomial Factorization Related Problems

Revision #1
Authors: Pranav Bisht, Ilya Volkovich
Accepted on: 14th July 2022 18:16
Downloads: 38
Keywords:

Abstract:

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.

### Paper:

TR22-070 | 8th May 2022 15:58

#### On Solving Sparse Polynomial Factorization Related Problems

TR22-070
Authors: Pranav Bisht, Ilya Volkovich
Publication: 9th May 2022 07:31
Downloads: 275
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint