TY - GEN
T1 - MEANDERS, RAMSEY THEORY AND LOWER BOUNDS FOR BRANCHING PROGRAMS.
AU - Alon, Noga
AU - Maass, Wolfgang
PY - 1986
Y1 - 1986
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 -