We determine the complexity of evaluating monotone Boolean functions in a variant of the decision tree model introduced in [Charikar et al. 2002]. In this model, reading different variables can incur different costs, and competitive analysis is employed to evaluate the performance of the algorithms. It is known that for a monotone Boolean function f, the size of the largest certificate, aka PROOF(f), is a lower bound for γ(f), the best possible competitiveness achievable by an algorithm on f. This bound has been proved to be achievable for some subclasses of the monotone Boolean functions, e.g., read once formulae, threshold trees. However, determining γ(f) for an arbitrary monotone Boolean function has so far remained a major open question, with the best known upper bound being essentially a factor of 2 away from the above lower bound. We close the gap and prove that for any monotone Boolean function f, γ(f) = PROOF(f). In fact, we prove that γ(f) ≤ PROOF(f) holds for a class much larger than the set of monotone Boolean functions. This class also contains all Boolean functions.

Function Evaluation via Linear Programming Approach in the Priced Information Model

CICALESE, Ferdinando;
2008-01-01

Abstract

We determine the complexity of evaluating monotone Boolean functions in a variant of the decision tree model introduced in [Charikar et al. 2002]. In this model, reading different variables can incur different costs, and competitive analysis is employed to evaluate the performance of the algorithms. It is known that for a monotone Boolean function f, the size of the largest certificate, aka PROOF(f), is a lower bound for γ(f), the best possible competitiveness achievable by an algorithm on f. This bound has been proved to be achievable for some subclasses of the monotone Boolean functions, e.g., read once formulae, threshold trees. However, determining γ(f) for an arbitrary monotone Boolean function has so far remained a major open question, with the best known upper bound being essentially a factor of 2 away from the above lower bound. We close the gap and prove that for any monotone Boolean function f, γ(f) = PROOF(f). In fact, we prove that γ(f) ≤ PROOF(f) holds for a class much larger than the set of monotone Boolean functions. This class also contains all Boolean functions.
2008
9783540705741
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1869328
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact