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