Incremental branching programs

DOI10.1007/S00224-007-9049-YMaRDI QIDQ929291zbMATH OpenOpenAlexFDO

Authors Anna Gál, Michal Koucký, Pierre McKenzie

Publication date 17 June 2008

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2006/623/

zbMATH Keywords

GEN problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Incremental Branching Programs
• scientific article; zbMATH DE number 17817
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Oracle branching programs and Logspace versus \(P^*\)
• scientific article; zbMATH DE number 1361505

Cites work

• A note on read-k times branching programs
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• An observation on time-storage trade off
• Branching Programs and Binary Decision Diagrams
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Complete problems for deterministic polynomial time
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• Incremental Branching Programs
• On lower bounds for read-\(k\)-times branching programs
• Oracle branching programs and Logspace versus \(P^*\)
• Relationships between nondeterministic and deterministic tape complexities
• Separation of the monotone NC hierarchy
• Space bounds for a game on graphs
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• Time-space tradeoffs for branching programs

Cited in

(6)

• Oracle branching programs and Logspace versus \(P^*\)
• Branching Programs for Tree Evaluation
• Incremental Branching Programs
• scientific article; zbMATH DE number 17817 (Why is no real title available?)
• scientific article; zbMATH DE number 1881085 (Why is no real title available?)
• Pebbles and branching programs for tree evaluation

This page was built for publication: Incremental branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q929291)