On the complexity of branching programs and decision trees for clique functions
From MaRDI portal
Publication:3798243
Recommendations
Cited in
(34)- Streaming and query once space complexity of longest increasing subsequence
- Almost \(k\)-wise independence and hard Boolean functions.
- Separating complexity classes related to \(\Omega\)-decision trees
- Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
- A simple function that requires exponential size read-once branching programs
- Separating complexity classes related to bounded alternating ?-branching programs
- A very simple function that requires exponential size read-once branching programs.
- Approximation of boolean functions by combinatorial rectangles
- On the size of binary decision diagrams representing Boolean functions
- Perspective on complexity measures targeting read-once branching programs
- Nonuniform complexity classes specified by lower and upper bounds
- The complexity of minimizing and learning OBDDs and FBDDs
- scientific article; zbMATH DE number 7453192 (Why is no real title available?)
- Forms of representation for simple games: sizes, conversions and equivalences
- scientific article; zbMATH DE number 3919835 (Why is no real title available?)
- On oblivious branching programs of linear length
- scientific article; zbMATH DE number 7455738 (Why is no real title available?)
- Efficient data structures for Boolean functions
- BDDs -- design, analysis, complexity, and applications.
- A lower bound on branching programs reading some bits twice
- Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- Lower bounds for linearly transformed OBDDs and FBDDs
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- Boolean expression diagrams
- scientific article; zbMATH DE number 1400211 (Why is no real title available?)
- Lower bounds for depth-restricted branching programs
- Communication Complexity and Lower Bounds on Multilective Computations
- Neither reading few bits twice nor reading illegally helps much
- New lower bounds and hierarchy results for restricted branching programs
- A note on read-$k$ times branching programs
- Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
- Time-space tradeoffs for branching programs
- scientific article; zbMATH DE number 4007722 (Why is no real title available?)
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)
