Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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