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

DOI10.1016/J.IPL.2007.11.009zbMath1186.68195OpenAlexW2080585858MaRDI QIDQ963361

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)

Related Items (1)

Exact OBDD bounds for some fundamental functions

Cites Work

• Unnamed Item
• Exact OBDD bounds for some fundamental functions
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Branching Programs and Binary Decision Diagrams
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing

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