https://hal.telecom-paris.fr/hal-03712198Amarilli, AntoineAntoineAmarilliINFRES - Département Informatique et Réseaux - Télécom ParisTechDIG - Data, Intelligence and Graphs - LTCI - Laboratoire Traitement et Communication de l'Information - IMT - Institut Mines-Télécom [Paris] - Télécom ParisAmsterdamer, YaelYaelAmsterdamerBar-Ilan University [Israël]Worst-case Analysis for Interactive Evaluation of Boolean ProvenanceHAL CCSD2022[INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB][INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO][INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Amarilli, Antoine2022-07-02 16:38:152022-07-11 15:36:572022-07-02 16:38:16enConference papers1In 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.