Name
Abstract | ||
|---|---|---|
We determine the complexity of evaluating monotone Booleanfunctions in a variant of the decision tree model introduced in[Charikar et al. 2002]. In this model, reading differentvariables can incur different costs, and competitive analysis isemployed to evaluate the performance of the algorithms. It is knownthat for a monotone Boolean function f, the size of thelargest certificate, aka PROOF(f), is a lowerbound for γ(f), the best possiblecompetitiveness achievable by an algorithm on f. Thisbound has been proved to be achievable for some subclasses of themonotone Boolean functions, e.g., read once formulae, thresholdtrees. However, determining γ(f) for anarbitrary monotone Boolean function has so far remained a majoropen question, with the best known upper bound being essentially afactor of 2 away from the above lower bound.We close the gap and prove that for any monotone Booleanfunction f, γ(f) =PROOF(f). In fact, we prove thatγ(f) ≤ PROOF(f) holdsfor a class much larger than the set of monotone Boolean functions.This class also contains all Boolean functions. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-70575-8_15 | ICALP |
Keywords | Field | DocType |
best possiblecompetitiveness,monotone booleanfunction,boolean function,monotone boolean function,different cost,decision tree model,aka proof,monotone booleanfunctions,priced information model,function evaluation via linear,competitive analysis,themonotone boolean function,decision tree,information model,lower bound,linear program,upper bound | Boolean function,Maximum satisfiability problem,Discrete mathematics,Combinatorics,Parity function,Boolean expression,Complete Boolean algebra,Boolean domain,Mathematics,Monotone polygon,Two-element Boolean algebra | Conference |
Volume | ISSN | Citations |
5125 | 0302-9743 | 3 |
PageRank | References | Authors |
0.41 | 15 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ferdinando Cicalese | 1 | 450 | 48.20 |
| Eduardo Sany Laber | 2 | 229 | 27.12 |