Approximation by DNF: Examples and Counterexamples

DOI10.1007/978-3-540-73420-8_19zbMath1171.94382OpenAlexW1564713837MaRDI QIDQ5428809

Karl Wimmer, Ryan O'Donnell

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)

Related Items (8)

Approximating Boolean Functions with Depth-2 Circuits ⋮ Unnamed Item ⋮ Advice Coins for Classical and Quantum Computation ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Variable Influences in Conjunctive Normal Forms ⋮ Parity helps to compute majority ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Harmonicity and invariance on slices of the Boolean cube

This page was built for publication: Approximation by DNF: Examples and Counterexamples