All reports by Author Neeraj Kayal:

__
TR22-151
| 12th November 2022
__

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey#### Low-depth arithmetic circuit lower bounds via shifted partials

__
TR21-155
| 13th November 2021
__

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

Revisions: 1

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving ... more >>>

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