MEANDERS, RAMSEY THEORY AND LOWER BOUNDS FOR BRANCHING PROGRAMS.

Noga Alon, Wolfgang Maass

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

A 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. It is demonstrated by studying the intrinsic complexity of the following set equality problem SE(n, m): Given a sequence x//1 , x//2 , . . . ,x//n , y//1 ,. . . ,y//n of 2//n numbers of m bits each, decide whether the sets x//1 ,. . . ,x//n and y//1 ,. . . ,y//n coincide. It is shown that for any log log n less than equivalent to m less than equivalent to (log n)/2, any input-oblivious sequential computation that solves SE(n, m) using 2**m/s space, takes OMEGA (n multiplied by (times) s) time.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages410-417
Number of pages8
ISBN (Print)0818607408, 9780818607400
DOIs
StatePublished - Jan 1 1986
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

Alon, N., & Maass, W. (1986). MEANDERS, RAMSEY THEORY AND LOWER BOUNDS FOR BRANCHING PROGRAMS. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 410-417). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE. https://doi.org/10.1109/sfcs.1986.31