All reports by Author Sumanta Ghosh:

__
TR18-036
| 21st February 2018
__

Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Towards blackbox identity testing of log-variate circuits

__
TR18-035
| 21st February 2018
__

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena#### Bootstrapping variables in algebraic circuits

__
TR17-035
| 23rd February 2017
__

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

Michael Forbes, Sumanta Ghosh, Nitin Saxena

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>