Near-optimal small-depth lower bounds for small distance connectivity
Near-optimal small-depth lower bounds for small distance connectivity
复制标题
短距离连接的接近最优的小深度下限
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
Xi Chen;I. Oliveira;R. Servedio;Li
本文证明了当k（n）≤ n时，用于判定一个n结点图是否有长度不超过k的s-to-t路的任何深度d回路的大小必须为nΩ（k1/d/d），当k（n）≤ n时，该回路的大小必须为nΩ（k1/5d/d）.之前的最佳电路尺寸下限是nkexp（−O（d））（由Beame，Impagliazzo，and Pitassi（Computational Complexity 1998））和nΩ（（logk）/d）（根据Rossman最近的公式尺寸下限（STOC 2014））。我们的下限非常接近最优，因为对于这个问题，一个简单的构造给出了大小为n 0（k2/d）的深度d电路（并且将我们的界限加强到nkΩ（1/d）需要证明无向连通性不在NC 1中）。我们的证明是通过减少到一个新的下限的小深度电路的大小计算的“Sipser函数”，在经典的电路下限发挥了重要作用的偏斜的变体。在我们证明这些类Sipser函数所需的下界时，一个关键因素是使用随机投影，这是Rossman，Servedio和Tan最近使用的随机限制的扩展（FOCS 2015）。随机预测使我们能够获得更清晰的定量界限，同时采用更简单的参数，在概念上和技术上，比以前的作品。
We show that any depth-d circuit for determining whether an n-node graph has an s-to-t path of length at most k must have size nΩ(k1/d/d) when k(n) ≤ n1/5, and nΩ(k1/5d/d) when k(n)≤ n. The previous best circuit size lower bounds were nkexp(−O(d)) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and nΩ((logk)/d) (following from a recent formula size lower bound of Rossman (STOC 2014)). Our lower bound is quite close to optimal, as a simple construction gives depth-d circuits of size nO(k2/d) for this problem (and strengthening our bound even to nkΩ(1/d) would require proving that undirected connectivity is not in NC1). Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the “Sipser functions” that have played an important role in classical circuit lower bounds. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections, an extension of random restrictions which were recently employed by Rossman, Servedio, and Tan (FOCS 2015). Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works.