BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1245
DTSTAMP:20230914T125956Z
SUMMARY:Polynomial time partition oracles for bounded degree planar graphs
DESCRIPTION:Speaker: Akash Kumar (EPFL Lausanne\, Switzerland.)\n\nAbstract
 : \nTake a planar graph with maximum degree d. These graphs admit a hyperf
 inite decompositions\, where\, for a sufficiently small \\epsilon > 0\, on
 e removes \\epsilon dn edges to get connected components of size independe
 nt of n. An important tool for sublinear algorithms and property testing f
 or such classes is the partition oracle. A partition oracle is a local pro
 cedure that gives "consistent" access to a hyperfinite decomposition\, wit
 hout any preprocessing. Given a query vertex v\, the partition oracle outp
 uts the component containing v in time independent of n. All the answers a
 re consistent with a single hyperfinite decomposition. In this talk\, I wi
 ll describe a partition oracle that runs in time poly(d/\\epsilon). I will
  also describe how this machinery strikes a fortune and helps in obtaining
  a tester for all planar properties which runs in time exp(d/epsilon^2). T
 his is easily obtained by a better error analysis on the seminal result of
  Newman and Sohler [SICOMP 2013].\nBased on Joint works with Sabyasachi Ba
 su\, C. Seshadhri and Andrew Stolman.\n
URL:https://www.tcs.tifr.res.in/web/events/1245
DTSTART;TZID=Asia/Kolkata:20221018T160000
DTEND;TZID=Asia/Kolkata:20221018T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR