2026-07-22T19:33:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9058 2024-03-06T10:43:15Z ddc:004 open_access

Towards Blackbox Identity Testing of Log-Variate Circuits Forbes, Michael A. Ghosh, Sumanta Saxena, Nitin hitting-set depth-3 diagonal derandomization polynomial identity testing log-variate concentration cone closed basis isolation 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. logarithmic 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Forbes and Sumanta Ghosh and Nitin Saxena 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.54 urn:nbn:de:0030-drops-90582 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.54 eng https://creativecommons.org/licenses/by/3.0/legalcode