Optimal bounds for the approximation of Boolean functions and some applications
From MaRDI portal
Recommendations
- Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness
- Approximating Boolean functions with depth-2 circuits
- Reviewing bounds on the circuit size of the hardest functions
- scientific article; zbMATH DE number 850402
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
Cites work
- scientific article; zbMATH DE number 3889430 (Why is no real title available?)
- scientific article; zbMATH DE number 3121508 (Why is no real title available?)
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 1261804 (Why is no real title available?)
- scientific article; zbMATH DE number 1142303 (Why is no real title available?)
- scientific article; zbMATH DE number 3225719 (Why is no real title available?)
- scientific article; zbMATH DE number 3390666 (Why is no real title available?)
- scientific article; zbMATH DE number 3059214 (Why is no real title available?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A UNIVERSAL PRINCIPLE OF SELF-CORRECTION
- A guided tour of Chernoff bounds
- Hardness vs randomness
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Information theory and the complexity of boolean functions
- Natural proofs
- On the complexity of realization of partial Boolean functions by circuits of functional elements
- Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness
Cited in
(19)- Reviewing bounds on the circuit size of the hardest functions
- Minimum \(\varepsilon\)-equivalent circuit size problem
- Database Support for Data Mining Applications
- Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness
- Approximating Boolean functions with depth-2 circuits
- On derandomization and average-case complexity of monotone functions
- Bounds for the number of Boolean functions admitting quadratic approximations of given accuracy
- Approximation of boolean functions by combinatorial rectangles
- Approximation of Boolean functions by local search
- scientific article; zbMATH DE number 1512688 (Why is no real title available?)
- Approximation of Boolean functions to Schaefer's classes
- Bounds for the number of Boolean functions admitting affine approximations of a given accuracy
- Rates of minimization of error functionals over Boolean variable-basis functions
- Approximating Boolean functions by OBDDs
- On approximation of maximally nonlinear Boolean functions by almost linear functions
- Algebraically degenerate approximations of Boolean functions
- Upper Bounds on Boolean-Width with Applications to Exact Algorithms
- Mathematical Foundations of Computer Science 2004
- scientific article; zbMATH DE number 6007902 (Why is no real title available?)
This page was built for publication: Optimal bounds for the approximation of Boolean functions and some applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1390872)
