To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.

jsMath
Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BHARGAV THANKEY:
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

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


TR22-099 | 14th July 2022
Nikhil Gupta, Chandan Saha, Bhargav Thankey

Equivalence Test for Read-Once Arithmetic Formulas

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


TR21-015 | 15th February 2021
Chandan Saha, Bhargav Thankey

Hitting Sets for Orbits of Circuit Classes and Polynomial Families

Revisions: 2

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


TR20-028 | 27th February 2020
Nikhil Gupta, Chandan Saha, Bhargav Thankey

A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

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




ISSN 1433-8092 | Imprint