EECS | Electrical Engineering and Computer Science

Faculty Candidate Seminar

Very Fast Approximation Algorithms for Big Graphs

Krzysztof Onak

Simons Postdoctoral Fellow, CMU
Carnegie Mellon University
Wednesday, February 22, 2012
4:00pm - 5:00pm
1690 Beyster Bldg.

Add to Google Calendar

About the Event

Sublinear-time algorithms attempt to infer information from a data set by accessing only a miniscule fraction of it. I will present examples of such algorithms with a particular focus on algorithms for approximating graph parameters. I will show a local computation technique that can be used to transform many classic greedy algorithms into sublinear-time algorithms. One example is an algorithm that computes a good additive approximation to the size of the maximum matching in time that depends only on the average degree of the graph and not the total number of vertices. Another example is a near-optimal algorithm for approximating the vertex cover size that runs in sublinear time even for very dense graphs. Our techniques also find applications to property testing, distributed algorithms, and local computation algorithms.


Krzysztof Onak is a Simons Postdoctoral Fellow at Carnegie Mellon University. He received his Ph.D. degree from the Massachusetts Institute of Technology in 2010. He is mostly interested in computation with limited resources, including sublinear-time algorithms, property testing, and streaming algorithms.

Additional Information

Contact: J. Patterson

Phone: 53495


Sponsor(s): CSE

Open to: Public