Name
Abstract | ||
|---|---|---|
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]. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-43948-7_20 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
computer and information science | Bernstein's theorem on monotone functions,Discrete mathematics,Combinatorics,Upper and lower bounds,Disjunctive normal form,Omega,Monotone boolean function,Mathematics,Monotone polygon | Conference |
Volume | ISSN | Citations |
8572 | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 20 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Blais | 1 | 286 | 22.49 |
| Johan Håstad | 2 | 3586 | 557.23 |
| Rocco A. Servedio | 3 | 1656 | 133.28 |
| Li-Yang Tan | 4 | 159 | 24.26 |