Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-056 | 20th May 2014 08:08

Factors of Sparse Polynomials are Sparse

RSS-Feed




Revision #1
Authors: Zeev Dvir, Rafael Mendes de Oliveira
Accepted on: 20th May 2014 08:08
Downloads: 433
Keywords: 


Abstract:

This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample to this paper’s main result in positive characteristic: If $F$ is a field with prime characteristic $p$, then the polynomial
$x_1^p + x_2^p + \ldots + x_n^p$ has the following factor:
$(x_1+x_2+ \ldots + x_n)^{p-1}$, which has sparsity $n^p$.



Changes to previous version:

We are withdrawing this paper.


Paper:

TR14-056 | 18th April 2014 18:08

Factors of Sparse Polynomials are Sparse





TR14-056
Authors: Zeev Dvir, Rafael Mendes de Oliveira
Publication: 18th April 2014 23:47
Downloads: 1181
Keywords: 


Abstract:

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$
has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees
of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial
bound holds in this case. Two immediate applications are a randomized quasi-polynomial time factoring algorithm for
sparse polynomials and a deterministic quasi-polynomial time algorithm for sparse divisibility.


Comment(s):

Comment #1 to TR14-056 | 23rd May 2014 10:17

Withdrawal of this paper

Authors: Rafael Mendes de Oliveira
Accepted on: 23rd May 2014 10:17
Keywords: 


Comment:

This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample
to this paper’s main result in positive characteristic: If $F$ is a field with prime characteristic $p$, then the polynomial
$x_1^p + x_2^p + \ldots + x^n^p$ has the following factor:
$(x_1+x_2+ \ldots + x_n)^{p-1}$, which has sparsity $n^p$.




ISSN 1433-8092 | Imprint