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.


About the EventSublineartime 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 sublineartime 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 nearoptimal 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. 
BiographyKrzysztof 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 sublineartime algorithms, property testing, and streaming algorithms. 
Additional Information
Contact: J. Patterson
Phone: 53495
Email: jeannecp@umich.edu
Event Sponsor: CSE
Open to: Public
