The optimal read-once branching program complexity for the direct storage access function
type: Item
instance of: scholarly article
title: The optimal read-once branching program complexity for the direct storage access function
zbMATH Open document ID: 1186.68195
author: Beate Bollig
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5694928
zbMATH Keywords: computational complexity
zbMATH Keywords: lower bounds
zbMATH Keywords: read-once branching programs
MaRDI profile type: Publication
full work available at URL: j.ipl.2007.11.009
OpenAlex ID: W2080585858
cites work: Exact OBDD bounds for some fundamental functions
cites work: A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing
cites work: Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
cites work: Q3762226
cites work: Branching Programs and Binary Decision Diagrams
DOI: 10.1016/J.IPL.2007.11.009
description: scientific article; zbMATH DE number 5694928