A&C Seminar: Jakub Tětek on "Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs"

Speaker: Jakub Tětek , University of Copenhagen

Date: Wednesday, May 04, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Seminar Room D463 (Star)

Event Type: Seminar

Room Description:

Host:

Contact: Rahul Ilango, rilango@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: A&C Seminar: Jakub Tětek on "Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs"

Title: Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs
Abstract: While algorithms for planar graphs have received a lot of attention, few papers have focused on the additional power that one gets from assuming an embedding of the graph is available. While in the classic sequential setting, this assumption gives no additional power, we show that this is far from being the case in other settings. Specifically, we focus on sublinear-time computation and massively parallel computation (MPC).

We show sublinear-time algorithms for approximating Lipschitz additive graph parameters. This includes, for example, the maximum matching, maximum independent set, or the minimum dominating set. We give a technique for designing MPC algorithms for embedded planar graphs that leads to O(1) round algorithms with O(n^{2/3+ε}) space per machine for: counting connected components, bipartition, minimum spanning tree problem, O(1)-approximate shortest paths, O(1)-approximate diameter/radius. Our results imply an improved MPC algorithm for Euclidean MST.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2022.

Created by Rahul Ilango Email at Saturday, April 30, 2022 at 12:44 PM.