ECCC-Report TR14-056https://eccc.weizmann.ac.il/report/2014/056Comments and Revisions published for TR14-056en-usFri, 23 May 2014 10:17:34 +0300
Comment 1
| Withdrawal of this paper |
Rafael Mendes de Oliveira
https://eccc.weizmann.ac.il/report/2014/056#comment1This 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$. Fri, 23 May 2014 10:17:34 +0300https://eccc.weizmann.ac.il/report/2014/056#comment1
Revision 1
| Factors of Sparse Polynomials are Sparse |
Rafael Mendes de Oliveira,
Zeev Dvir
https://eccc.weizmann.ac.il/report/2014/056#revision1This 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$. Tue, 20 May 2014 08:08:58 +0300https://eccc.weizmann.ac.il/report/2014/056#revision1
Paper TR14-056
| Factors of Sparse Polynomials are Sparse |
Rafael Mendes de Oliveira,
Zeev Dvir
https://eccc.weizmann.ac.il/report/2014/056We 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.Fri, 18 Apr 2014 23:47:33 +0300https://eccc.weizmann.ac.il/report/2014/056