A very simple function that requires exponential size read-once branching programs.

DOI10.1016/S0020-0190(98)00042-8zbMath1078.68633OpenAlexW2070290122MaRDI QIDQ2583538

Beate Bollig, Ingo Wegener

Publication date: 17 January 2006

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00042-8

zbMATH Keywords

Computational complexityBoolean sumsRead-once branching programsProblem of Zarankiewicz

Mathematics Subject Classification ID

Related Items (5)

Communication Complexity and Lower Bounds on Multilective Computations ⋮ Knowledge compilation meets database theory: compiling queries to decision diagrams ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ Size of OBDD representation of 2-level redundancies functions ⋮ On converting CNF to DNF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple function that requires exponential size read-once branching programs
• Graph driven BDDs -- a new data structure for Boolean functions
• Entropy of contact circuits and lower bounds on their complexity
• Some remarks on Boolean sums
• A new lower bound on the monotone network complexity of Boolean sums
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• On lower bounds for read-\(k\)-times branching programs
• On the complexity of branching programs and decision trees for clique functions
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• On a problem of K. Zarankiewicz

This page was built for publication: A very simple function that requires exponential size read-once branching programs.