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