An Average-Case Depth Hierarchy Theorem for Boolean Circuits
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
复制标题
布尔电路的平均情况深度层次定理
DOI：
10.1145/3095799
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
Benjamin Rossman;R. Servedio;Li
基于AND、OR和NOT门的标准基，我们证明了布尔电路的平均情况下的深度层次定理。我们的分层定理说，对于每一个d≥2，都有一个显式的n元布尔函数f，它是由一个线性大小深度-d公式计算的，这使得任何深度-(d-1)电路在所有输入的分数(1/2+on(1))上满足f必有大小exp(nΩ(1/d))。这回答了Hastad在他的博士论文[Has86b]中提出的一个公开问题。我们的平均情形深度层次定理表明，多项式层次相对于概率为1的随机预言是无穷的，从而证实了Hastad[Has86a]、Cai[Cai86]和Babai[Bab87]的猜想。我们还利用我们的结果证明了与Linial、Mansour、Nisan[LMN93]和Boppana[Bop97]关于恒定深度电路总影响的结果不存在“近似逆”，从而回答了Kalai[Kal12]和Hatami[Hat14]提出的一个问题。我们证明中的一个关键成分是随机投影的概念，它推广了随机限制。
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d - 1) circuit that agrees with f on (1/2 + on(1)) fraction of all inputs must have size exp(nΩ(1/d)). This answers an open question posed by Hastad in his Ph.D. thesis [Has86b]. Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Hastad [Has86a], Cai [Cai86], and Babai [Bab87]. We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan [LMN93] and Boppana [Bop97] on the total influence of constant-depth circuits, thus answering a question posed by Kalai [Kal12] and Hatami [Hat14]. A key ingredient in our proof is a notion of random projections which generalize random restrictions.