Time-space tradeoffs for branching programs

DOI10.1006/jcss.2001.1778zbMath1052.68049OpenAlexW2001736707MaRDI QIDQ1604208

Michael E. Saks, T. S. Jayram, P. W. Beame

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1778

zbMATH Keywords

Boolean function

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

On multi-partition communication complexity ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ Expanders and time-restricted branching programs ⋮ A note on the decoding complexity of error-correcting codes ⋮ Totally optimal decision trees for Boolean functions ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ Incremental branching programs ⋮ A nondeterministic space-time tradeoff for linear codes ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Choice-memory tradeoff in allocations ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Unnamed Item ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple function that requires exponential size read-once branching programs
• Time-space trade-offs for branching programs
• A lower bound for read-once-only branching programs
• Meanders and their applications in lower bounds arguments
• Time-space tradeoffs for algebraic problems on general sequential machines
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Fundamentals of computation theory. 8th international conference, FCT '91, Gosen, Germany, September 9--13, 1991. Proceedings
• The computational complexity of universal hashing
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• On lower bounds for read-\(k\)-times branching programs
• Determinism versus non-determinism for linear time RAMs (extended abstract)
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Graph-Based Algorithms for Boolean Function Manipulation
• A Time-Space Tradeoff for Element Distinctness
• On the complexity of branching programs and decision trees for clique functions
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation

This page was built for publication: Time-space tradeoffs for branching programs