Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
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
Identifiers
URN: urn:nbn:se:kth:diva-166367DOI: 10.1007/978-3-662-43948-7_20ISI: 000352643300022Scopus ID: 2-s2.0-84904165616ISBN: 978-3-662-43948-7 (print)OAI: oai:DiVA.org:kth-166367DiVA: diva2:810589
Conference
41st International Colloquium on Automata, Languages and Programming, July 08-11, 2014, Copenhagen, Denmark
Note

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

Authority records BETA

Håstad, Johan

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 27 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf