Approximation of boolean functions by combinatorial rectangles

DOI10.1016/S0304-3975(02)00568-6MaRDI QIDQ1399979zbMATH OpenOpenAlexFDO

Authors Martin Sauerhoff

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

zbMATH Keywords

lower boundsapproximationnondeterminismcommunication complexityrandomnessbranching programs

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• scientific article; zbMATH DE number 1962823
• Stochastic Algorithms: Foundations and Applications
• Optimal bounds for the approximation of Boolean functions and some applications
• Scientific article; zbMATH DE number 2102760

Cites work

• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 4170851 (Why is no real title available?)
• scientific article; zbMATH DE number 4068270 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1500514 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• scientific article; zbMATH DE number 1775457 (Why is no real title available?)
• A note on read-$k$ times branching programs
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Computational Complexity of Probabilistic Turing Machines
• Determinism versus non-determinism for linear time RAMs (extended abstract)
• Different Modes of Communication
• Expressing combinatorial optimization problems by linear programs
• Making Nondeterminism Unambiguous
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• On lower bounds for read-\(k\)-times branching programs
• On the complexity of branching programs and decision trees for clique functions
• On the distributional complexity of disjointness
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• Relative complexity of checking and evaluating
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Some observations on the probabilistic algorithms and NP-hard problems
• Time-space tradeoffs for branching programs
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Weak Random Sources, Hitting Sets, and BPP Simulations

Cited in

(8)

• scientific article; zbMATH DE number 7559127 (Why is no real title available?)
• Inner and outer rounding of Boolean operations on lattice polygonal regions
• Connecting knowledge compilation classes and width parameters
• Bounds for the number of Boolean functions admitting quadratic approximations of given accuracy
• Perspective on complexity measures targeting read-once branching programs
• Approximation of Boolean functions to Schaefer's classes
• Bounds for the number of Boolean functions admitting affine approximations of a given accuracy
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs

This page was built for publication: Approximation of boolean functions by combinatorial rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399979)