Sublinear-Time Algorithms
Lecturer:
Krzysztof Onak
(IBM T.J.Watson Research Center, USA).
About the lecturer | Course Summary | Assignment
About the lecturer:
Krzysztof Onak is a computer scientist who works at the IBM T.J. Watson Research Center. He is mostly interested in computation with limited resources, including sublinear-time algorithms, property testing, and streaming algorithms. He received his Master's degree from the University of Warsaw and his PhD degree from the Massachusetts Institute of Technology. Before joining IBM, he was a Simons Postdoctoral Fellow at Carnegie Mellon University.
Krzysztof has a soft spot for the University of Warsaw. He looks forward to visiting it again. While he was a student here, he represented it in programming competitions and won the ACM International Collegiate Programming Contest.
Course summary: Given the sizes of modern data sets, it is natural to ask if we can design very efficient algorithms that operate under significantly limited computational resources. Sublinear-time algorithms attempt a seemingly impossible challenge: to solve a problem in time sublinear in the input size. In particular, they do not have enough time even to read the entire input.
I will present many examples of such algorithms, which provide a meaningful approximate answer by employing random sampling and exploiting the structure of the problem. I will also discuss limitations of these methods, mention related models, and state a number of compelling open questions.
Topics that will be covered include:
- montonicity testing (i.e., checking whether a sequence is approximately sorted);
- approximating graph parameters (average degree, minimum spanning tree cost, vertex cover and maximum matching size, etc.);
- distribution testing (sample question: is an unknown distribution uniform?).
Assignment: You can find the problem set here. Please send the solutions to the address provided on the problem sheet by Wednesday, June 3.