BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/189
DTSTAMP:20230914T125914Z
SUMMARY:Quantum Query Complexity of Minor-closed Graph Properties
DESCRIPTION:Speaker: Robin Kothari\nUniversity of Waterloo\nInstitute for Q
 uantum Computing\n200 University Ave. West\nWaterloo\, Ontar\n\nAbstract: 
 \nWe study the quantum query complexity of minor-closed graph properties\,
  which include such problems as determining whether a graph is planar\, is
  a forest\, or does not contain a path of a given length. We show that mos
 t minor-closed properties---those that cannot be characterized by a finite
  set of forbidden subgraphs---have quantum query complexity \\\\Theta(n^{3
 /2}). To establish this\, we prove an adversary lower bound using a detail
 ed analysis of the structure of minor-closed properties with respect to fo
 rbidden topological minors and forbidden subgraphs. On the other hand\, we
  show that minor-closed properties (and more generally\, sparse graph prop
 erties) that can be characterized by finitely many forbidden subgraphs can
  be solved strictly faster\, in o(n^{3/2}) queries. Our algorithms are a n
 ovel application of the quantum walk search framework and give improved up
 per bounds for several subgraph-finding problems.\n
URL:https://www.tcs.tifr.res.in/web/events/189
DTSTART;VALUE=DATE:20110427
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR