Improved depth lower bounds for small distance connectivity

We consider the problem of determining, given a graph G with specified node s 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 c ircuits requires depth Omega(log log k), improving on a depth lower bound o f Omega(log* k) when k = log(O(1))n given by Ajtai (1989), Bellantoni et al . (1992). More generally, we obtain an improved size-depth tradeoff lower b ound for the problem for all k less than or equal to log n. The key to our technique is a new form of "switching lemma" which combines some of the fea tures of iteratively shortening terms due to Furst et al. (1984) and Ajtai (1983) with the features of switching lemma arguments introduced by Yao (19 85), Hastad (1987), and Cai (1986) that have been the methods of choice for subsequent results.