All reports by Author Bhargav Thankey:

__
TR21-015
| 15th February 2021
__

Chandan Saha, Bhargav Thankey#### Hitting Sets for Orbits of Circuit Classes and Polynomial Families

__
TR20-028
| 27th February 2020
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

Chandan Saha, Bhargav Thankey

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set ... more >>>

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>>