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