SCS Recruiting Seminar: Krzysztof Onak

Event Details
  • Date/Time:
    • Tuesday February 4, 2020 - Wednesday February 5, 2020
      11:00 am - 11:59 am
  • Location: KACB 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:

Tess Malone, Communications Officer


Summary Sentence: Algorithmic Challenges of Modern Distributed Data

Full Summary: No summary paragraph submitted.

  • Krzysztof Onak Krzysztof Onak

 TITLE: Algorithmic Challenges of Modern Distributed Data


Growing amounts of collected and processed data, on the one hand, and throughput, real-time response, and privacy constraints, on the other hand, increasingly lead to computing systems in which the entirety of data is no longer local to any single processing unit. Both cloud computing and computing at the edge pose new unique algorithmic challenges. How does one minimize the number of communication rounds, total information exchanged, and surplus computation while still providing answers in a timely manner?

Apart from giving an overview of the variety of arising challenges, this talk will focus on new techniques developed for processing frameworks similar to MapReduce and Spark. We will show how to obtain significant improvements on direct implementations of classic or straightforward algorithms for graph combinatorial optimization problems and computing PageRank. Our techniques allow for compressing several rounds of computation into exponentially fewer rounds of MapReduce computation. In particular, this line of work has led to the first approximate maximum matching algorithms with sublogarithmic round complexity when the space per machine is linear or sublinear in the number of nodes in the graph.

This is a very quickly developing area of research and many intriguing questions remain open.


Krzysztof Onak is a research scientist in the Mathematics of AI group at the IBM T.J. Watson Research Center. His main research interests concern big data computation with limited resources, including algorithms for modern parallel and distributed systems, sublinear-time algorithms, and streaming. Onak received his master’s degree from the University of Warsaw and his Ph.D. from the Massachusetts Institute of Technology. Before joining IBM, he was a Simons Postdoctoral Fellow at Carnegie Mellon University.


Additional Information

In Campus Calendar

College of Computing, School of Computer Science

Invited Audience
Faculty/Staff, Postdoc, Public, Graduate students, Undergraduate students
No keywords were submitted.
  • Created By: Tess Malone
  • Workflow Status: Published
  • Created On: Jan 27, 2020 - 3:30pm
  • Last Updated: Jan 27, 2020 - 3:31pm