Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

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

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

ISSN 1433-8092 | Imprint