All reports by Author Bhargav Thankey:

__
TR22-151
| 12th November 2022
__

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

__
TR22-099
| 14th July 2022
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### Equivalence Test for Read-Once Arithmetic Formulas

__
TR21-015
| 15th February 2021
__

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

Revisions: 2

__
TR20-028
| 27th February 2020
__

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

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

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two $n$-variate polynomials $f, g \in \mathbb{F}[\mathbf{x}]$ are equivalent, denoted ... more >>>

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