Approximating matching size from random streams

Speaker: Michael Kapralov , MIT

Date: Wednesday, December 18, 2013

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

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Joanne Talbot Hanley, 3-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

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

Reminder Subject: TALK: Algorithms and Complexity Seminar: Michael Kapralov "Approximating matching size from random streams"

We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore O~(n?) approximation with polylogarithmic space in an n vertex graph and a constant approximation with ?(n) space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in n.

Our algorithm is obtained by effecting a streaming implementation of a simple “local” algorithm that we design for this problem. The local algorithm produces a O(k?n1/k) approximation to the size of a maximum matching by exploring the radius k neighborhoods of vertices, for any parameter k. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for k=?(logn/loglogn). Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems.

This is joint work with Sanjeev Khanna and Madhu Sudan

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Joanne Talbot Hanley at Wednesday, December 04, 2013 at 1:11 PM.