On the complexity of branching programs and decision trees for clique functions
From MaRDI portal
Publication:3798243
DOI10.1145/42282.46161zbMath0652.68063OpenAlexW2162199822WikidataQ56210449 ScholiaQ56210449MaRDI QIDQ3798243
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
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)
Related Items
The complexity of minimizing and learning OBDDs and FBDDs, A simple function that requires exponential size read-once branching programs, Communication Complexity and Lower Bounds on Multilective Computations, Efficient data structures for Boolean functions, Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice, Neither reading few bits twice nor reading illegally helps much, A lower bound on branching programs reading some bits twice, Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access, Approximation of boolean functions by combinatorial rectangles, Almost \(k\)-wise independence and hard Boolean functions., Forms of representation for simple games: sizes, conversions and equivalences, Separating complexity classes related to bounded alternating ?-branching programs, Unnamed Item, Unnamed Item, BDDs -- design, analysis, complexity, and applications., Lower bounds for depth-restricted branching programs, A note on read-$k$ times branching programs, On the size of binary decision diagrams representing Boolean functions, Separating complexity classes related to \(\Omega\)-decision trees, New lower bounds and hierarchy results for restricted branching programs, Boolean expression diagrams, Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs, Nonuniform complexity classes specified by lower and upper bounds, A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs, A very simple function that requires exponential size read-once branching programs., On oblivious branching programs of linear length, Time-space tradeoffs for branching programs, Lower bounds for linearly transformed OBDDs and FBDDs
