Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-036 | 21st February 2018 15:39

Towards blackbox identity testing of log-variate circuits

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint