Evasive Boolean function
= Evasive Boolean function
{title2=$D(f)=n$}
A <Boolean function> is evasive when every deterministic <decision tree> computing it has a worst-case path that queries all input bits. The <alternating-sum criterion for decision-tree evasiveness> is one sufficient method for proving this lower bound.