Seminars
View all Seminars | Download ICal for this eventPlanar Partition Oracles and When they strike gold: An exp(1/epsilon^2) Tester for All Planar Properties
Series: Theory Seminar
Speaker: Akash Kumar, Postdoctoral Researcher, Theoretical Computer Science, EPFL, Switzerland,
Date/Time: Jan 21 17:00:00
Location: Microsoft Teams - ON-LINE
Faculty Advisor:
Abstract:
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.
Microsoft Teams Link:
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
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Speaker Bio:
Host Faculty: Dr. Anand Louis