首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Towards blackbox identity testing of log-variate circuits
  • 本地全文:下载
  • 作者:Michael Forbes ; Sumanta Ghosh ; Nitin Saxena
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 n ). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly ( s 2 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.

  • 关键词:Basis isolating Weight Assignment ; Cone Closed Basis ; depth-3 diagonal circuit ; Hitting Set ; log-variate ; Low Cone Concentration ; polynomial identity testing ; Rank Concentration
国家哲学社会科学文献中心版权所有