2015/09/24 by Xi Chen, Chen, Xi, Igor C. Oliveira +5
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1509.07476
arxiv created 2015/09/24 · arxiv updated 2015/09/25
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). The previous best circuit size lower bounds for this problem were n^kexp(-O(d)) (due to Beame, Impagliazzo, and Pitassi [BIP98]) and nΩ((log k)/d) (following from a recent formula size lower bound of Rossman [Ros14]). Our lower bound is quite close to optimal, since a simple construction gives depth-d circuits of size n^O(k2/d) for this problem (and strengthening our bound even to n^kΩ(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 [Sip83, Yao85, Hås86]. 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 in [RST15]. Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works [Ajt89, BPU92, BIP98, Ros14].