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:

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:

For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Anand Louis