TR18-052 Authors: Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Publication: 16th March 2018 03:38

Downloads: 919

Keywords:

In 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.