Meanders, Ramsey theory and lower bounds for branching programs
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 410-417
- https://doi.org/10.1109/sfcs.1986.31
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machinesThe Journal of Symbolic Logic, 1988
- Two lower bounds for branching programsPublished by Association for Computing Machinery (ACM) ,1986
- A lower bound on complexity of branching programsPublished by Springer Nature ,1984
- Lower bounds by probabilistic argumentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Lower bounds for algebraic computation treesPublished by Association for Computing Machinery (ACM) ,1983
- Multi-party protocolsPublished by Association for Computing Machinery (ACM) ,1983
- A Time-Space Tradeoff for Sorting on a General Sequential Model of ComputationSIAM Journal on Computing, 1982
- Superconcentrators of depth 2Journal of Computer and System Sciences, 1982