Oliveira, Rafael
Factors of Low Individual Degree Polynomials
Abstract
In [Kaltofen, 1989], Kaltofen proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in [Kopparty/Saraf/Shpilka,CCC'14], and the question of bounding the depth of the circuits computing the factors of a polynomial.
We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. We show that if P(x_1, ..., x_n) is a polynomial with individual degrees bounded by r that can be computed by a formula of size s and depth d, then any factor f(x_1, ..., x_n) of P(x_1, ..., x_n) can be computed by a formula of size poly((rn)^r, s) and depth d+5. This partially answers the question above posed in [Kopparty/Saraf/Shpilka,CCC'14], that asked if this result holds without the exponential dependence on r. Our work generalizes the main factorization theorem from Dvir et al. [Dvir/Shpilka/Yehudayoff,SIAM J. Comp., 2009], who proved it for the special case when the factors are of the form f(x_1, ..., x_n) = x_n  g(x_1, ..., x_n1). Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas).
BibTeX  Entry
@InProceedings{oliveira:LIPIcs:2015:5059,
author = {Rafael Oliveira},
title = {{Factors of Low Individual Degree Polynomials}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {198216},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5059},
URN = {urn:nbn:de:0030drops50594},
doi = {10.4230/LIPIcs.CCC.2015.198},
annote = {Keywords: Arithmetic Circuits, Factoring, Algebraic Complexity}
}
2015
Keywords: 

Arithmetic Circuits, Factoring, Algebraic Complexity 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 