TY - GEN

T1 - MEANDERS, RAMSEY THEORY AND LOWER BOUNDS FOR BRANCHING PROGRAMS.

AU - Alon, Noga

AU - Maass, Wolfgang

PY - 1986/1/1

Y1 - 1986/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022917772&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022917772&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1986.31

DO - 10.1109/sfcs.1986.31

M3 - Conference contribution

AN - SCOPUS:0022917772

SN - 0818607408

SN - 9780818607400

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 410

EP - 417

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -