Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case

Ferdinando Cicalese, Travis Gagie, Eduardo Sany Laber, Martin Milanic

Introduction

In the field of "priced information," researchers study scenarios where obtaining data comes at a cost. A classic analogy is a physician diagnosing a patient: each medical test provides a piece of information but incurs a specific cost. The goal is to determine the final diagnosis (represented by a Boolean function $f$) by performing the most cost-effective sequence of tests.

This problem, known as Boolean function evaluation, is typically analyzed through the lens of competitive analysis. We compare the cost incurred by an online algorithm (which chooses tests sequentially without knowing the results) against the cost of the cheapest "proof" or certificate—the minimum set of variables that would have confirmed the result if their values were known in advance. While this area is well-developed for monotone functions, where the function's output changes predictably as inputs increase, the non-monotone case has remained largely unexplored. This paper provides the first non-trivial bounds and characterizations for these more complex functions.

The Framework: Competitive Analysis and LPA

The authors define the extremal competitive ratio, $\gamma(f)$, as the best performance a deterministic algorithm can guarantee across all possible cost assignments. To analyze this, they utilize a Linear Programming Approach (LPA). Originally developed for monotone functions, the LPA constructs a linear program over the set of all possible certificates for a function.

A significant contribution of this work is demonstrating the robustness of the LPA. Despite being designed for the simpler monotone case, the framework proves effective for non-monotone functions, suggesting it may serve as a universal tool for evaluating Boolean functions under cost constraints. To establish lower bounds, the authors also employ adversary strategies, constructing specific variable assignments that force algorithms to exceed the cost of a minimal proof.

Symmetric Functions and the Power of "Spread"

One of the paper's primary breakthroughs is the exact characterization of symmetric Boolean functions. These are functions where the output depends solely on the number of inputs set to 1, rather than which specific inputs are active (e.g., Majority or Parity functions).

The authors identify a structural property called the "spread" ($s(f)$), defined as the maximum width of an interval of inputs for which the function's value remains constant. They prove a definitive result: for any symmetric function, the competitive ratio is exactly equal to its spread ($\gamma(f) = s(f)$). Furthermore, they show that a simple greedy algorithm—querying variables in increasing order of cost—is optimal for this class of functions, providing a polynomial-time solution to a previously open problem.

Beyond Monotonicity: Breaking the Certificate Bound

In the study of monotone functions, the competitive ratio is closely tied to the size of the largest certificate ($PROOF(f)$). However, this paper reveals that non-monotonicity fundamentally changes this relationship.

The authors demonstrate that for arbitrary functions, the competitive ratio $\gamma(f)$ is not necessarily bounded by $PROOF(f)$. A striking example is the Parity function. To "prove" the parity of $n$ variables, one must know the value of every single variable, meaning $PROOF(f) = n$. Yet, the authors show that the competitive ratio for Parity is actually 1. This highlights a counter-intuitive reality: non-monotonicity can sometimes make a function easier to evaluate competitively, even when its certificates are large.

For the class of quadratic Boolean functions (functions representable in Disjunctive Normal Form where each term has at most two variables), the authors establish a bounded relationship: $$2 \le \sup_{f \in Q} \frac{PROOF(f)}{\gamma(f)} \le 3$$ This result provides a concrete bound for a specific non-monotone class while reinforcing the discovery that the maximum certificate size is no longer an upper bound for the competitive ratio in the general case.

Conclusion and Future Directions

This research significantly advances the understanding of priced information by moving beyond the restriction of monotonicity. By solving the symmetric case and providing bounds for quadratic functions, the authors lay the groundwork for a more general theory of Boolean function evaluation.

Several intriguing questions remain for future study:

  1. The Integrality Question: Observations suggest that the extremal competitive ratio $\gamma(f)$ might always be an integer. Whether this holds for all Boolean functions remains an open formal question.
  2. General Characterization: While symmetric functions are now understood, a unified theory that characterizes the competitive ratio for any arbitrary Boolean function remains elusive.
  3. Bounded Degree Extensions: A logical next step is extending the quadratic results to functions of "bounded degree" $k$, where DNF terms contain at most $k$ variables.

Summary updated

Abstract

We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.
BibTeX
@article{cicalese2011competitive,
  author = {Ferdinando Cicalese and Travis Gagie and Eduardo Sany Laber and Martin Milanic},
  title = {{Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case}},
  journal = {Discret. Appl. Math.},
  year = {2011},
  doi = {10.1016/j.dam.2010.05.016},
}
Figure