Approximation by DNF: Examples and Counterexamples
From MaRDI portal
Recommendations
- Approximating Boolean functions with depth-2 circuits
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- On DNF approximators for monotone Boolean functions
- Approximation of biased Boolean functions of small total influence by DNFs
- Improved approximation of linear threshold functions
Cited in
(19)- Harmonicity and invariance on slices of the Boolean cube
- The complexity of DNF of parities
- Advice coins for classical and quantum computation
- Approximating Boolean functions with depth-2 circuits
- Variable Influences in Conjunctive Normal Forms
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Improved approximation of linear threshold functions
- Approximation of biased Boolean functions of small total influence by DNFs
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- A polynomial lower bound for testing monotonicity
- Depth two majority circuits for majority and list expanders
- Parity helps to compute majority
- On DNF approximators for monotone Boolean functions
- DNF sparsification beyond sunflowers
- Optimal explicit small-depth formulas for the coin problem
- Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
- Size bounds on low depth circuits for promise majority
- How to share an NP statement or combiners for zero-knowledge proofs
- A technique for hardness amplification against AC^0
This page was built for publication: Approximation by DNF: Examples and Counterexamples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428809)
