A direct-sum theorem for read-once branching programs

DOI10.4230/LIPICS.APPROX-RANDOM.2016.44MaRDI QIDQ4636478zbMATH OpenOpenAlexFDO

Authors

Publication date 19 April 2018

Full work available at URL https://dblp.uni-trier.de/db/conf/approx/approx2016.html#RaoS16

zbMATH Keywords

direct-suminformation complexitystreaming algorithms

Mathematics Subject Classification ID

Data structures (68P05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The optimal read-once branching program complexity for the direct storage access function
• scientific article; zbMATH DE number 2079872
• scientific article; zbMATH DE number 2102760
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• An exponential lower bound for real-time branching programs

Cited in

(3)

• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• scientific article; zbMATH DE number 2079872 (Why is no real title available?)
• Read-Once Branching Programs for Tree Evaluation Problems

This page was built for publication: A direct-sum theorem for read-once branching programs

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