On the complexity of branching programs and decision trees for clique functions
DOI10.1145/42282.46161zbMATH Open0652.68063OpenAlexW2162199822WikidataQ56210449 ScholiaQ56210449MaRDI QIDQ3798243FDOQ3798243
Authors: Ingo Wegener 
Publication date: 1988
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/42282.46161
Recommendations
branching programscomplexity hierarchiespolynomial lower boundsclique functionsBoolean decision-treesequences of Boolean functions
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (34)
- Neither reading few bits twice nor reading illegally helps much
- Lower bounds for linearly transformed OBDDs and FBDDs
- Lower bounds for depth-restricted branching programs
- New lower bounds and hierarchy results for restricted branching programs
- A note on read-$k$ times branching programs
- Almost \(k\)-wise independence and hard Boolean functions.
- Title not available (Why is that?)
- Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
- The complexity of minimizing and learning OBDDs and FBDDs
- Approximation of boolean functions by combinatorial rectangles
- Efficient data structures for Boolean functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- A lower bound on branching programs reading some bits twice
- Streaming and query once space complexity of longest increasing subsequence
- A simple function that requires exponential size read-once branching programs
- A very simple function that requires exponential size read-once branching programs.
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- Communication Complexity and Lower Bounds on Multilective Computations
- Separating complexity classes related to bounded alternating ?-branching programs
- Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
- Boolean expression diagrams
- On the size of binary decision diagrams representing Boolean functions
- Title not available (Why is that?)
- Perspective on complexity measures targeting read-once branching programs
- Title not available (Why is that?)
- Time-space tradeoffs for branching programs
- Separating complexity classes related to \(\Omega\)-decision trees
- Nonuniform complexity classes specified by lower and upper bounds
- On oblivious branching programs of linear length
- Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
- Forms of representation for simple games: sizes, conversions and equivalences
- BDDs -- design, analysis, complexity, and applications.
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
This page was built for publication: On the complexity of branching programs and decision trees for clique functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798243)
