Approximation by DNF: Examples and Counterexamples

DOI10.1007/978-3-540-73420-8_19MaRDI QIDQ5428809zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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
• Harmonicity and invariance on slices of the Boolean cube
• DNF sparsification beyond sunflowers
• 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
• Improved approximation of linear threshold functions
• Depth two majority circuits for majority and list expanders
• 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)