Tata Institute of Fundamental Research
Evasiveness and the Music of Primes
Seminar
Speaker:
Raghav Kulkarni
University of Chicago
1100 E 58th Street
Chicago, IL 60637
United States of America
http:
Date:
Thursday, 17 Sep 2009 (all day)
Venue:
A-269 (TAP Seminar Room)
(Scan to add to calendar)
Abstract:
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 if 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).
| Speaker: | Raghav Kulkarni University of Chicago 1100 E 58th Street Chicago, IL 60637 United States of America http: |
| Date: | Thursday, 17 Sep 2009 (all day) |
| Venue: | A-269 (TAP Seminar Room) |
(Scan to add to calendar)
Abstract:
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 if 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).
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).