Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-036 | 21st February 2018 15:39

#### Towards blackbox identity testing of log-variate circuits

TR18-036
Authors: Michael Forbes, Sumanta Ghosh, Nitin Saxena
Publication: 21st February 2018 16:25
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 variables, eg.~logarithm in the size $s$.
We give the first poly($s$)-time blackbox identity test for $n=O(\log s)$ variate size-$s$ circuits that have poly($s$)-dimensional partial derivative space; eg.~depth-$3$ diagonal circuits (or $\Sigma\wedge\Sigma^n$). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly$(s2^n)$-time identity test was known before us. We introduce the concept of {\em cone-closed} basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.