The optimal read-once branching program complexity for the direct storage access function

DOI10.1016/J.IPL.2007.11.009MaRDI QIDQ963361zbMATH OpenOpenAlexFDO

Authors Beate Bollig

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.11.009

zbMATH Keywords

computational complexitylower boundsread-once branching programs

Mathematics Subject Classification ID

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

Recommendations

• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 1962822
• scientific article; zbMATH DE number 3919835
• A read-once branching program lower bound of \({\omega}(2^{n/4})\) for integer multiplication using universal hashing
• Time-space trade-offs for branching programs

Cites work

• A read-once branching program lower bound of \({\omega}(2^{n/4})\) for integer multiplication using universal hashing
• Branching Programs and Binary Decision Diagrams
• Exact OBDD bounds for some fundamental functions
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions

Cited in

(3)

• A lower bound for read-once-only branching programs
• Exact OBDD bounds for some fundamental functions
• A direct-sum theorem for read-once branching programs

This page was built for publication: The optimal read-once branching program complexity for the direct storage access function

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