  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.
