BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220121T120000Z
UID:9c9f0b879f8b33d9dbfab346366b2f16-237
DTSTAMP:19700101T120017Z
DESCRIPTION:Planar Partition Oracles and When they strike gold: An exp(1/epsilon^2) Tester for All Planar Properties
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/237/planar-partition-oracles-and-when-they-strike-gold-an-exp1-epsilon2-tester-for-all-planar-properties/
SUMMARY:Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small ϵ > 0, one removes ϵdn edges to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle. A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. In this talk, I will describe a partition oracle that runs in time poly(d/ϵ). I will also describe how this machinery strikes a fortune and helps in obtaining a constant time tester for all planar properties. This is easily obtained by a better error analysis on the seminal result of Newman and Sohler [SICOMP 2013]. Based on Joint works with Sabyasachi Basu, C. Seshadhri and Andrew Stolman.
<br>
<br>
Microsoft Teams Link:
<br>
<a href="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d</a>
<br>
 <br>
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
DTSTART:20220121T120000Z
END:VEVENT
END:VCALENDAR