ECCC-Report TR18-052https://eccc.weizmann.ac.il/report/2018/052Comments and Revisions published for TR18-052en-usFri, 16 Mar 2018 03:38:49 +0200
Paper TR18-052
| Some Closure Results for Polynomial Factorization and Applications |
Chi-Ning Chou,
Mrinal Kumar,
Noam Solomon
https://eccc.weizmann.ac.il/report/2018/052In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class $VP$ is closed under taking factors. A natural question in this context is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, bounded depth arithmetic circuits or the class $VNP$, are closed under taking factors.
In this paper, we show that all factors of degree at most $\log^a n$ of polynomials with poly$(n)$ size depth $k$ circuits have poly$(n)$ size circuits of depth at most $O(k + a)$. This partially answers a question of Shpilka-Yehudayoff and has applications to hardness-randomness tradeoffs for bounded depth arithmetic circuits.
More precisely, this shows that a superpolynomial lower bound for bounded depth arithmetic circuits, for a family of explicit polynomials of degree poly$(\log n)$ implies deterministic sub-exponential time algorithms for polynomial identity testing (PIT) for bounded depth arithmetic circuits. This is incomparable to a beautiful result of Dvir et al. [DSY09], where they showed that super-polynomial lower bounds for constant depth arithmetic circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for bounded depth circuits of \emph{bounded individual degree}. Thus, we remove the ``bounded individual degree" condition in [DSY09] at the cost of strengthening the hardness assumption to hold for polynomials of \emph{low} degree.
As direct applications of our techniques, we also obtain simple proofs of the following results.
\begin{itemize}
\item The complexity class $VNP$ is closed under taking factors. This confirms a conjecture of B{\"u}rgisser , and improves upon a recent result of Dutta, Saxena and Sinhababu who showed a quasipolynomial upper bound on the number of auxiliary variables and the complexity of the verifier circuit of factors of polynomials in $VNP$.
\item A factor of degree at most $d$ of a polynomial $P$ which can be computed by an arithmetic formula (resp. algebraic branching program) of size $s$ has a formula (resp. algebraic branching program) of size at most poly$(s, d^{\log d}, deg(P))$. This result was first shown by Dutta et al., and we obtain a slightly different proof as an easy consequence of our techniques.
\end{itemize}
Our proofs rely on a combination of the \emph{lifting} based ideas developed in polynomial factoring literature and the depth reduction results for arithmetic circuits, and hold over fields of characteristic zero or sufficiently large.
Fri, 16 Mar 2018 03:38:49 +0200https://eccc.weizmann.ac.il/report/2018/052