Approximation by DNF: Examples and Counterexamples
From MaRDI portal
Publication:5428809
DOI10.1007/978-3-540-73420-8_19zbMATH Open1171.94382OpenAlexW1564713837MaRDI QIDQ5428809FDOQ5428809
Authors: Ryan O'Donnell, Karl Wimmer 
Publication date: 28 November 2007
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://figshare.com/articles/journal_contribution/Approximation_by_DNF_Examples_and_Counterexamples/6603614
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 (16)
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- DNF sparsification beyond sunflowers
- Harmonicity and invariance on slices of the Boolean cube
- The complexity of DNF of parities
- Parity helps to compute majority
- Approximation of biased Boolean functions of small total influence by DNFs
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- On DNF approximators for monotone Boolean functions
- Advice coins for classical and quantum computation
- Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
- Optimal explicit small-depth formulas for the coin problem
- Depth two majority circuits for majority and list expanders
- Improved approximation of linear threshold functions
- Variable Influences in Conjunctive Normal Forms
- A polynomial lower bound for testing monotonicity
- Approximating Boolean functions with depth-2 circuits
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)
