Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

We show an $\Omega \left(\frac{n^3}{(\ln n)^2}\right)$ lower bound on the size of any depth three ($\SPS$) arithmetic circuit computing an explicit multilinear polynomial in $n$ variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson.

more >>>morris yau

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$

on $N = \Theta(n polylog(n))$

variables with degree $N$ being in VP such that every

$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.

We ...
more >>>