Skip to Main content Skip to Navigation
Conference papers

Worst-case Analysis for Interactive Evaluation of Boolean Provenance

Abstract : In recent work, we have introduced a framework for fine-grained consent management in databases, which combines Boolean data provenance with the field of interactive Boolean evaluation. In turn, interactive Boolean evaluation aims at unveiling the underlying truth value of a Boolean expression by frugally probing the truth values of individual values. The required number of probes depends on the Boolean provenance structure and on the (a-priori unknown) probe answers. Prior work has analyzed and aimed to optimize the expected number of probes, where expectancy is with respect to a probability distribution over probe answers. This paper gives a novel worst-case analysis for the problem, inspired by the decision tree depth of Boolean functions. Specifically, we introduce a notion of evasive provenance expressions, namely expressions, where one may need to probe all variables in the worst case. We show that read-once expressions are evasive, and identify an additional class of expressions (acyclic monotone 2-DNF) for which evasiveness may be decided in PTIME. As for the more general question of finding the optimal strategy, we show that it is coNP-hard in general. We are still able to identify a sub-class of provenance expressions that is "far from evasive", namely, where an optimal worst-case strategy probes only log(n) out of the n variables in the expression, and show that we can find this optimal strategy in polynomial time.
Complete list of metadata
Contributor : Antoine Amarilli Connect in order to contact the contributor
Submitted on : Saturday, July 2, 2022 - 4:38:15 PM
Last modification on : Monday, July 11, 2022 - 3:36:57 PM

Links full text


  • HAL Id : hal-03712198, version 1
  • ARXIV : 2205.04224



Antoine Amarilli, Yael Amsterdamer. Worst-case Analysis for Interactive Evaluation of Boolean Provenance. TaPP workshop, Jun 2022, Philadelphia, United States. ⟨hal-03712198⟩



Record views