Seminars

View all Seminars  |  Download ICal for this event

Planar 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