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) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s.
We give the first poly(s)-time blackbox identity test for size s and n=O(logs) variate depth-3 diagonal circuits (or Σ∧Σn). The former model is well-studied but no poly(s2n)-time identity test was known before us. We introduce the concept of 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.
It is joint work with Michael A. Forbes and Nitin Saxena.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
