Function Evaluation Via Linear Programming in the Priced Information Model

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.