@inproceedings{6f16a88954a5421a9ca26509c80feb46,
title = "Towards blackbox identity testing of log-variate circuits",
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. 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 ∧n). The former model is well-studied (Nisan,Wigderson, FOCS'95) 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.",
keywords = "Basis isolation, Concentration, Cone closed, Depth-3, Derandomization, Diagonal, Hitting-set, Log-variate, Polynomial identity testing",
author = "Forbes, {Michael A.} and Sumanta Ghosh and Nitin Saxena",
note = "Publisher Copyright: {\textcopyright} Michael A. Forbes, Sumanta Ghosh, and Nitin Saxena;.; 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 ; Conference date: 09-07-2018 Through 13-07-2018",
year = "2018",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2018.54",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christos Kaklamanis and Daniel Marx and Ioannis Chatzigiannakis and Donald Sannella",
booktitle = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018",
}