Improved depth lower bounds for small distance connectivity
Paul W. Beame, Russell Impagliazzo, Toniann Pitassi · 2002
We consider the problem of determining, given a graph G and specified nodes s and t, whether or not there is a path of at most k edges in G from s to t. We show that solving this problem on polynomial-size unbounded fan-in circuits, requires depth /spl Omega/(loglogk), improving on a depth lower bound of n(log*k) when k=log/sup O(1/) n. In addition we show that there is a constant c such that for k/spl les/logn, any depth d unbounded fan-in circuit for this problem requires size at least n/sup ck/spl epsiv/d/ where /spl epsiv//sub d/=/spl phi//sup -2d//3 and /spl phi/ is the golden mean. This latter result improves on an n/sup /spl Omega/(log(d+3/k)) bound where log/sup (i/) is the i-fold composition of log with itself. The key to our technique is a new form of switching lemma which combines some of the features of iteratively shortening terms due to Furst, Saxe, and Sipser (1981) and Ajtai (1983) with the kinds of switching lemma arguments introduced by Yao (1985), Hastad (1986), and Cai (1986) that have been the methods of choice for subsequent results.