An exponential lower bound for real-time branching programs

DOI10.1016/S0019-9958(86)80018-3MaRDI QIDQ3763592zbMATH OpenFDO

Authors Stanislav Zak

Publication date 1986

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(86)80018-3

zbMATH Keywords

Real-time branching programssequential computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3928350
• scientific article; zbMATH DE number 3890736
• Lower bounds on the complexity of real-time branching programs
• scientific article; zbMATH DE number 4094813
• Time-space trade-offs for branching programs

Cited in

(9)

• Time-space trade-offs for branching programs
• A lower bound on branching programs reading some bits twice
• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 3928350 (Why is no real title available?)
• scientific article; zbMATH DE number 4055052 (Why is no real title available?)
• Lower bounds on the complexity of real-time branching programs
• scientific article; zbMATH DE number 4094813 (Why is no real title available?)
• Communication Complexity and Lower Bounds on Multilective Computations
• A direct-sum theorem for read-once branching programs

This page was built for publication: An exponential lower bound for real-time branching programs

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