All reports by Author Chandan Saha:

__
TR21-155
| 13th November 2021
__

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha#### Learning generalized depth-three arithmetic circuits in the non-degenerate case

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Consider a homogeneous degree $d$ polynomial $f = T_1 + \cdots + T_s$, $T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$ where $g_i$'s are homogeneous $m$-variate degree $d$ polynomials and $\ell_{i,j}$'s are linear polynomials in $n$ variables. We design a (randomized) learning algorithm that given black-box access to $f$, computes black-boxes for ... more >>>