A simple function that requires exponential size read-once branching programs
From MaRDI portal
Recommendations
- A very 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
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- A lower bound for read-once-only branching programs
Cites work
- scientific article; zbMATH DE number 3890736 (Why is no real title available?)
- scientific article; zbMATH DE number 3919835 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (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?)
- A lower bound for read-once-only branching programs
- A note on read-$k$ times branching programs
- Entropy of contact circuits and lower bounds on their complexity
- On lower bounds for read-\(k\)-times branching programs
- On the complexity of branching programs and decision trees for clique functions
- Parity, circuits, and the polynomial-time hierarchy
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(12)- The simplified weighted sum function and its average sensitivity
- Size of OBDD representation of 2-level redundancies functions
- Lower bounds for linearly transformed OBDDs and FBDDs
- Almost \(k\)-wise independence and hard Boolean functions.
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
- A very simple function that requires exponential size read-once branching programs.
- Streaming and query once space complexity of longest increasing subsequence
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- Perspective on complexity measures targeting read-once branching programs
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- Time-space tradeoffs for branching programs
- A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
This page was built for publication: A 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 Q287023)
