A non-linear time lower bound for Boolean branching programs
Author:
- M. AjtaiMAM. Ajtai
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 60-70
Abstract
No abstract availableThis publication has 6 references indexed in Scilit:
- Time-space tradeoffs for branching programs2002
- Determinism versus non-determinism for linear time RAMs (extended abstract)1999
- On separating the read-k-times branching program hierarchy1998
- On lower bounds for read-k-times branching programscomputational complexity, 1993
- A general Sequential Time-Space Tradeoff for Finding Unique ElementsSIAM Journal on Computing, 1991
- A Time-Space Tradeoff for Sorting on a General Sequential Model of ComputationSIAM Journal on Computing, 1982