3.30 p.m.
Evasiveness and the Music of Primes
Raghav Kulkarni
University of Chicago.
11-09-09

---

Abstract

Keywords: Decision Tree Lower Bound, Evasiveness, Group Actions, Simplicial Complex, Goldbach Conjecture)

A boolean function f on N variables is called "evasive" if its 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 which 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 a longstanding (35+ years) 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 technical contribution here is in 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.