Towards blackbox identity testing of log-variate circuits
Towards blackbox identity testing of log-variate circuits
复制标题
DOI：
10.4230/lipics.icalp.2018.54
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Michael A. Forbes;Sumanta K Ghosh;Nitin Saxena
中科院分区：
文献类型：
--
作者：
Michael A. Forbes;Sumanta K Ghosh;Nitin Saxena
[12]黑盒身份测试的去随机化简化为极其特殊的电路模型。经过13一行的工作，我们知道，专注于电路与恒定的深度和不断许多14变量是不够的（阿格拉瓦尔，高希，Saxena，STOC'18），以获得一般击中集和电路15下界。这启发我们去研究变量少的电路，例如。在大小s上的对数。[16]我们给出了n = O（log s）变量大小电路17的第一个poly（s）时间黑盒恒等式检验，该电路具有poly（s）维偏导数空间;例如。深度为3的对角线电路（或称对角线电路）。[18]前一个模型已经得到了很好的研究（Nisan，Wigderson，FOCS'95），但是在我们之前还没有poly（s 2 n）-时间恒等式[19]检验。本文介绍了锥闭基隔离的概念，并证明了它在研究对数变量电路中的有用性。它包含了先前在ROABP模型背景下广泛研究的秩-浓度21概念。22
12 Derandomization of blackbox identity testing reduces to extremely special circuit models. After 13 a line of work, it is known that focusing on circuits with constant-depth and constantly many 14 variables is enough (Agrawal,Ghosh,Saxena, STOC’18) to get to general hitting-sets and circuit 15 lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s . 16 We give the first poly( s )-time blackbox identity test for n = O (log s ) variate sizes circuits 17 that have poly( s )-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Σ ∧ Σ n ). 18 The former model is well-studied (Nisan,Wigderson, FOCS’95) but no poly( s 2 n )-time identity 19 test was known before us. We introduce the concept of cone-closed basis isolation and prove its 20 usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration 21 studied extensively in the context of ROABP models. 22