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

DOI10.1016/S0020-0190(98)00042-8MaRDI QIDQ2583538zbMATH OpenOpenAlexFDO

Authors 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

Boolean sumsComputational complexityProblem of ZarankiewiczRead-once branching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A simple function that requires exponential size read-once branching programs
• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• scientific article; zbMATH DE number 1361490
• A lower bound for read-once-only branching programs
• Stochastic Algorithms: Foundations and Applications

Cites work

• A new lower bound on the monotone network complexity of Boolean sums
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• A simple function that requires exponential size read-once branching programs
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• Entropy of contact circuits and lower bounds on their complexity
• Graph driven BDDs -- a new data structure for Boolean functions
• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 4047113 (Why is no real title available?)
• scientific article; zbMATH DE number 4094813 (Why is no real title available?)
• scientific article; zbMATH DE number 1263188 (Why is no real title available?)
• scientific article; zbMATH DE number 549860 (Why is no real title available?)
• scientific article; zbMATH DE number 1361490 (Why is no real title available?)
• scientific article; zbMATH DE number 3387244 (Why is no real title available?)
• On a problem of K. Zarankiewicz
• On lower bounds for read-\(k\)-times branching programs
• On the complexity of branching programs and decision trees for clique functions
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Some remarks on Boolean sums

Cited in

(13)

• A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
• A lower bound for read-once-only branching programs
• Almost \(k\)-wise independence and hard Boolean functions.
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• On converting CNF to DNF
• A simple function that requires exponential size read-once branching programs
• Knowledge compilation meets database theory: compiling queries to decision diagrams
• Communication Complexity and Lower Bounds on Multilective Computations
• scientific article; zbMATH DE number 1361490 (Why is no real title available?)
• Size of OBDD representation of 2-level redundancies functions
• Streaming and query once space complexity of longest increasing subsequence
• Perspective on complexity measures targeting read-once branching programs
• Explicit directional affine extractors and improved hardness for linear branching programs

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

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