CS Events

PhD Defense

Factoring and Learning Algorithms for Low-depth Algebraic Circuits.


Download as iCal file

Tuesday, April 12, 2022, 09:00am - 10:00am


Speaker: Vishwas Bhargava

Location : Via Zoom


Shubhangi Saraf (chair)

Eric Allender

Sepehr Assadi

Zeev Dvir (external)

Event Type: PhD Defense

Abstract: Polynomial factoring and learning arithmetic circuits (a.k.a. circuit-reconstruction) are two fundamental problems in algebraic complexity. They are deeply connected to the questions of circuit lower bound and polynomial identity testing (PIT). In this dissertation, we present various new results on learning and factoring of low-depth circuits, while emphasizing these connections. Some of our main results are as follows:1. Sparse Polynomial Factoring: We study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \Fn$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\poly(d)\log n}$. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular we show if $f$ is an $s$-sparse polynomial in $n$ variables, with individual degrees of its variables bounded by $d$, then the sparsity of each factor of $f$ is bounded by $s^{\BigO({d^2\log{n}})}$. 2. Learning low-rank tensors and depth 3 multilinear circuits: We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when the input is a {\em constant-rank} tensor.3. Learning depth-4 multilinear circuits over finite Fields: We present a deterministic algorithm for reconstructing multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. For any fixed $k$, given black-box access to a polynomial $f \in \Fn$ computable by a multilinear $\Spsp(k)$ circuit of size $s$, the algorithm runs in time quasi-poly($n,s,\size{\F})$ and outputs a multilinear $\Spsp(k)$ circuit of size quasi-poly($n,s$) that computes $f$.4. Average-case learning for generalized depth-3 circuits: We design a (randomized) learning algorithm for \textit{generalized} depth-3 circuits. A circuit in this class is an expression of the type, $g_1(\ell_{11}, \ldots, \ell_{1m}) + \cdots + g_s(\ell_{s1}, \ldots, \ell_{sm}),$ where $g_i$'s are $m$-variate degree $d$ homogeneous polynomials and $\ell_{ij}$'s are linear forms in the variables $\vecx = (x_1,\ldots, x_n)$. Our work is in line with the ideas presented in \cite{KayalSaha19, GargKayalSaha20} where they use lower bound methods in arithmetic complexity to design average-case learning algorithms.


Rutgers University School of Arts and Sciences

Contact  Eric Allender