Tata Institute of Fundamental Research
Polynomial time partition oracles for bounded degree planar graphs
STCS Colloquium
Speaker:
Akash Kumar (EPFL Lausanne, Switzerland.)
Organiser:
Umang Bhaskar
Date:
Tuesday, 18 Oct 2022, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small \epsilon > 0, one removes \epsilon 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/\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). 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.
| Speaker: | Akash Kumar (EPFL Lausanne, Switzerland.) |
| Organiser: | Umang Bhaskar |
| Date: | Tuesday, 18 Oct 2022, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small \epsilon > 0, one removes \epsilon 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/\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). 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.
Based on Joint works with Sabyasachi Basu, C. Seshadhri and Andrew Stolman.