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