BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/31
DTSTAMP:20230914T125907Z
SUMMARY:Evasiveness and the Music of Primes
DESCRIPTION:Speaker: Raghav Kulkarni\nUniversity of Chicago\n1100 E 58th St
reet\nChicago\, IL 60637\nUnited States of America\nhttp:\n\nAbstract: \nA
boolean function f on N variables is called evasive if its decision tre
e complexity is N\, i.e.\, one must query *all* the variables (in worst ca
se) 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 und
er the relabeling of vertices. A graph property is called monotone if it i
s 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.\n\nWe confirm the evasiveness of several monotone graph
properties under widely accepted number theoretic hypotheses (e.g. General
ized Riemann Hypothesis\, Chowla's Conjecture on smallest Dirichlet primes
etc). In particular\, we show:\n\n(a) forbidden subgraph is evasive for a
ll large enough n\n\n(b) any montone property of sparse graphs (< n^{3/2 -
\\\\epsilon} edges) is evasive.\n\nEven our weaker unconditional results
rely on some deep and interesting properties of the integers such as Vinog
radov's theorem on Goldbach conjecture asserting that every odd integer ca
n be expressed as the sum of three primes. Our main technical contribution
here is in connecting the topological framework of Kahn\, Saks and Sturte
vant 84\,(further developed by Chakrabarti\, Khot and Shi 02)\, to analyti
c number theory via better analysis (e.g. using Weil's character sum estim
ates) 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).\n
URL:https://www.tcs.tifr.res.in/web/events/31
DTSTART;VALUE=DATE:20090917
LOCATION:A-269 (TAP Seminar Room)
END:VEVENT
END:VCALENDAR