Approximating Boolean functions with depth-2 circuits
From MaRDI portal
Recommendations
- Approximation by DNF: Examples and Counterexamples
- On DNF approximators for monotone Boolean functions
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Optimal bounds for the approximation of Boolean functions and some applications
- On Improved Degree Lower Bounds for Polynomial Approximation.
Cites work
- scientific article; zbMATH DE number 3831858 (Why is no real title available?)
- scientific article; zbMATH DE number 5852793 (Why is no real title available?)
- scientific article; zbMATH DE number 3170312 (Why is no real title available?)
- scientific article; zbMATH DE number 3827756 (Why is no real title available?)
- scientific article; zbMATH DE number 3916176 (Why is no real title available?)
- scientific article; zbMATH DE number 1024657 (Why is no real title available?)
- scientific article; zbMATH DE number 3430531 (Why is no real title available?)
- scientific article; zbMATH DE number 3085175 (Why is no real title available?)
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Approximation by DNF: Examples and Counterexamples
- Constant depth circuits, Fourier transform, and learnability
- Covering codes with improved density
- Learning intersections and thresholds of halfspaces
- On the Correlation of Parity and Small-Depth Circuits
- Parity, circuits, and the polynomial-time hierarchy
- The average sensitivity of an intersection of half spaces
- The average sensitivity of bounded-depth circuits
- The shortest disjunctive normal form of a random Boolean function
- Tight bounds on the average sensitivity of k-CNF
- Variable Influences in Conjunctive Normal Forms
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(10)- The complexity of DNF of parities
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Optimal bounds on the approximation of Boolean functions with consequences on the concept of hardness
- On DNF approximators for monotone Boolean functions
- Approximating Boolean functions by OBDDs
- Approximation by DNF: Examples and Counterexamples
- Mathematical Foundations of Computer Science 2004
- Asymptotically best method for synthesis of Boolean recursive circuits
- On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
This page was built for publication: Approximating Boolean functions with depth-2 circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3451753)
