Evasiveness through a circuit lens
Raghav Kulkarni · 2013
A function f : {0, 1}n -> {0, 1} is called evasive if its decision tree complexity is maximal, i.e., D(f) = n. The long-standing Anderaa-Rosenberg-Karp (ARK) Conjecture asserts that every non-trivial monotone graph property is evasive. The Evasiveness Conjecture (EC) is a generalization of ARK Conjecture from monotone graph properties to arbitrary monotone transitive Boolean functions.