Property Testing in Planar Graphs: Bipartiteness and Subgraph Freeness

Speaker: Christian Sohler

Date: Wednesday, February 05, 2020

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

Public: Yes

Location: Seminar Room G575

Event Type: Seminar

Room Description:

Host: Quanquan Liu, Sitan Chen, NIkhil Vyas

Contact: Quanquan Liu, quanquan@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: Property Testing in Planar Graphs: Bipartiteness and Subgraph Freeness

Property testing in planar bounded degree graphs is well understood.
However, the algorithms depend heavily on the assumption that the input
graph has bounded degree and cannot be used for general planar graphs.

In this line of work we study testability of properties of general planar
graphs. We first show that a random walk based approach can be used to
obtain a bipartiteness tester with constant query complexity. Then we
explain a modified random neighborhood exploration that can be used to
test subgraph freeness.

(Joint work with Artur Czumaj, Morteza Monemizadeh and Krzysztof Onak)

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2019-2020 .

Created by Quanquan Liu Email at Tuesday, February 04, 2020 at 12:16 PM.