Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-168 | 8th December 2014 22:25

Deterministically Factoring Sparse Polynomials into Multilinear Factors

RSS-Feed




TR14-168
Authors: Ilya Volkovich
Publication: 8th December 2014 23:29
Downloads: 878
Keywords: 


Abstract:

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors.
Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in \cite{GathenKaltofen85} to devise an efficient deterministic algorithm for factoring (general) sparse polynomials.
We achieve our goal by introducing \emph{essential factorization schemes} which can be thought of a relaxation of the regular factorization notion.



ISSN 1433-8092 | Imprint