Approximation of boolean functions by combinatorial rectangles
From MaRDI portal
Publication:1399979
DOI10.1016/S0304-3975(02)00568-6zbMath1022.68133OpenAlexW2085830992MaRDI QIDQ1399979
Publication date: 30 July 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00568-6
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some observations on the probabilistic algorithms and NP-hard problems
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Expressing combinatorial optimization problems by linear programs
- On the distributional complexity of disjointness
- Relative complexity of checking and evaluating
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Time-space tradeoffs for branching programs
- On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
- On lower bounds for read-\(k\)-times branching programs
- Determinism versus non-determinism for linear time RAMs (extended abstract)
- Different Modes of Communication
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- On the complexity of branching programs and decision trees for clique functions
- Computational Complexity of Probabilistic Turing Machines
- Weak Random Sources, Hitting Sets, and BPP Simulations
- A note on read-$k$ times branching programs
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- Communication Complexity
- Making Nondeterminism Unambiguous
- On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
This page was built for publication: Approximation of boolean functions by combinatorial rectangles
