Evasiveness and the music of prime numbers

decision tree complexity is N, i.e., one must query *all* the variables in worst case
in order to decide if f(X) = 1. A graph property of n-vertex graphs is a
boolean function on N = n \choose 2 variables that is invariant under the relabeling
of vertices. A graph property is called monotone is it is closed under
deletion of edges, e.g. planarity, 3-colorability etc. The following
conjecture due Aanderaa-Rosenberg-Karp is an outstanding open question:
every non-trivial monotone graph property must be evasive.
An important special case is the class of properties given by a "forbidden
subgraph," i.e. all n vertex graphs which do not contain a fixed subgraph H.

We confirm the evasiveness of several monotone graph properties under widely
accepted number theoretic hypotheses (e.g. Generalized Riemann Hypothesis,
Chowla's Conjecture on smallest Dirichlet primes etc). In particular, we show:
(a) forbidden subgraph is evasive for all large enough n
(b) any montone property of sparse graphs (< n^{3/2 - \epsilon} edges) is
evasive.

Even our weaker unconditional results rely on some deep and interesting properties of the integers such as Vinogradov's theorem on Goldbach conjecture asserting that every odd integer can be expressed as the sum of three primes. Our main contribution here is connecting the topological framework of Kahn, Saks and Sturtevant 84,(further developed by Chakrabarti, Khot and Shi 02), to analytic number theory via better analysis (e.g. using Weil's character sum estimates) of the orbital structure of permutation groups and their connection to the distribution of prime numbers.

This is a joint work with Laci Babai, Anandam Banerjee and Vipul Naik.