Change search
ReferencesLink to record
Permanent link

Direct link
On DNF Approximators for Monotone Boolean Functions
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2014 (English)In: Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, Springer Berlin/Heidelberg, 2014, Vol. 8572, 235-246 p.Conference paper (Refereed)
Abstract [en]

We study the complexity of approximating monotone Boolean functions with disjunctive normal form (DNF) formulas, exploring two main directions. First, we construct DNF approximators for arbitrary monotone functions achieving one-sided error: we show that every monotone f can be e-approximated by a DNF g of size 2(n-Omega)(root n) satisfying g(x) <= f(x) for all x is an element of{0, 1}(n). This is the first non-trivial universal upper bound even for DNF approximators incurring two-sided error. Next, we study the power of negations in DNF approximators for monotone functions. We exhibit monotone functions for which non-monotone DNFs perform better than monotone ones, giving separations with respect to both DNF size and width. Our results, when taken together with a classical theorem of Quine [1], highlight an interesting contrast between approximation and exact computation in the DNF complexity of monotone functions, and they add to a line of work on the surprising role of negations in monotone complexity [2,3,4].

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2014. Vol. 8572, 235-246 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 8572
Keyword [en]
Boolean functions, Approximators, Classical theorems, Disjunctive normal form, Exact computations, Monotone Boolean functions, Monotone functions, Non-trivial, Upper Bound
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-166367DOI: 10.1007/978-3-662-43948-7_20ISI: 000352643300022ScopusID: 2-s2.0-84904165616ISBN: 978-3-662-43948-7OAI: diva2:810589
41st International Colloquium on Automata, Languages and Programming, July 08-11, 2014, Copenhagen, Denmark

QC 20150507

Available from: 2015-05-07 Created: 2015-05-07 Last updated: 2015-05-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link