Time-space tradeoffs for branching programs

Paul Beame, Michael Saks, Jayram S. Thathachar

Research output: Contribution to journalConference article

29 Scopus citations

Abstract

We obtain the first non-trivial time-space tradeoff lower bound for functions f : {0,1}n→{0,1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length (1+ε)n, for some constant ε>0. We also give the first separation result between the syntactic and semantic read-k models for k>1 by showing that polynomial-size semantic read-twice branching programs call compute functions that require exponential size on any syntactic read-k branching program. We also show a time-space tradeoff result on the more general R-way branching program model: for any k, we give a function that requires exponential size to be computed by length kn q-way branching programs, for some q = q(k).

Original languageEnglish (US)
Pages (from-to)254-263
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1998
Externally publishedYes
EventProceedings of the 1998 39th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 8 1998Nov 11 1998

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Time-space tradeoffs for branching programs'. Together they form a unique fingerprint.

  • Cite this