A non-linear time lower bound for Boolean branching programs

Publisher Website

20 January 2003

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

https://doi.org/10.1109/sffcs.1999.814578

Abstract

No abstract available

This publication has 6 references indexed in Scilit:

Time-space tradeoffs for branching programs
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Determinism versus non-determinism for linear time RAMs (extended abstract)
Published by Association for Computing Machinery (ACM) ,1999
On separating the read-k-times branching program hierarchy
Published by Association for Computing Machinery (ACM) ,1998
On lower bounds for read-k-times branching programs
computational complexity, 1993
A general Sequential Time-Space Tradeoff for Finding Unique Elements
SIAM Journal on Computing, 1991
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
SIAM Journal on Computing, 1982