Meanders, Ramsey theory and lower bounds for branching programs

A novel technique for obtaining lower bounds for the time versus space complexity of certain functions in a general input oblivious sequential model of computation is developed. This is demonstrated by studying the intrinsic complexity of the following set equality problem SE(n,m): Given a sequence x1,x2,....,xn, y1,....,yn of 2n numbers of m bits each, decide whether the sets [x1,....,xn] and [y1,...,yn] coincide. We show that for any log log n ≤ m ≤1/2log n and any 1 ≤ s ≤ log n, any input oblivious sequential computation that solves SE(n,m) using 2m/s space, takes Ω(n ? s) time. This result is sharp for all admissible values of n,m,s and is the first known nontrivial time space tradeoff lower bound (for space = ω (log n) of a set recognition problem on such a general model of computation. Our method also supplies lower bounds on the length of arbitrary (not necessarily input oblivious) branching programs for several natural symmetric functions, improving results of Chandra, Furst and Lipton, of Pudlák and of Ajtai et. al. For example we show that for the majority - function any branching program of width w(n) has length ω(n · log w/n (n) · log w (n)), in particular for bounded width we get length ω (n log n) (independently of our work Babai et. al. [BPRS] have simultaneously proved this last result). Our lower bounds for branching programs imply lower bounds on the number of steps that are needed to pebble arbitrary computation graphs for the same computational problems. To establish our lower bounds we introduce the new concept of a meander that captures superconcentrator-type properties of sequences. We prove lower bounds on the length of meanders via a new Ramsey theoretic lemma that is of interest in its own right. This lemma has other applications, including a tight lower bound on the size of weak superconcentrators of depth 2 that strengthens the known lower bound of Pippenger [Pi]. A surprising new feature of these applications of Ramsey theory in lower bound arguments is the fact that no numbers are required to be unusually large and that several of the resulting superlinear lower bounds are in fact optimal.