Krzysztof Onak

I am an assistant professor in the Faculty of Computing & Data Sciences at Boston University. Previously, I was a researcher at the IBM T.J. Watson Research Center, a Simons Postdoctoral Fellow at CMU, and a PhD student at MIT.

My interests include theoretical foundations of algorithms for big data and their applications to AI and machine learning. Among many other things, I have worked on algorithms for modern parallel and distributed frameworks and streaming and sublinear-time algorithms. During my time in industry, I designed and implemented efficient algorithms with strong empirical performance and solid theoretical backing across a variety of applied projects.

• Email: krzysztof@onak.pl (personal, research) / konak@bu.edu (BU matters, research)
• Postdocs and students:
  • Esty Kelman (postdoc, co-hosted)
  • Themistoklis Haris (PhD student)
  • Zi Song Yeoh (PhD student)
  • Dragos Ristache (PhD 2026)
• All publications (DBLP, Google Scholar) and select publications:
  • Walking Randomly, Massively, and Efficiently (with Jakub Łącki, Slobodan Mitrović, and Piotr Sankowski)
    The 52th ACM Symposium on Theory of Computing (STOC 2020).
    [distributed and parallel computation]
    
  • Scalable Fair Clustering (with Arturs Backurs, Piotr Indyk, Baruch Schieber, Ali Vakilian, and Tal Wagner)
    The 36th International Conference on Machine Learning (ICML 2019).
    [fairness]
    
  • Round Compression for Parallel Matching Algorithms (with Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, and Piotr Sankowski)
    The 50th ACM Symposium on Theory of Computing (STOC 2018).
    [distributed and parallel computation]
    
  • Parallel Algorithms for Geometric Graph Problems (with Alexandr Andoni, Aleksandar Nikolov, and Grigory Yaroslavtsev)
    The 46th ACM Symposium on Theory of Computing (STOC 2014).
    [distributed and parallel computation]
    
  • Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity (with Alexandr Andoni and Robert Krauthgamer)
    The 51st Annual Symposium on Foundations of Computer Science (FOCS 2010).
    [edit distance approximation]
    
  • Maintaining a Large Matching and a Small Vertex Cover (with Ronitt Rubinfeld)
    The 42nd ACM Symposium on Theory of Computing (STOC 2010).
    [dynamic graph algorithms]
    
  • Constant-Time Approximation Algorithms via Local Improvements (with Huy N. Nguyen)
    The 49th Annual Symposium on Foundations of Computer Science (FOCS 2008).
    [sublinear-time graph algorithms]
    
• Teaching:
  • Algorithmic Techniques for Taming Big Data (Spring 2025)
  • Algorithms for Data Science (Fall 2023)
  • Programming for Data Science (Spring 2022)
• SUBLINEAR.INFO: a list of open problems in sublinear algorithms
• Events I co-organized:
  • Workshop on Emerging Models of Colossal Computation (E=mc²) (co-organizer)
  • Workshop on Local Algorithms (WOLA 2022) (PC chair)
  • Simons Semesters on Algorithms for the Massive Parallel Computation Model (co-organizer)
  • New York Area Theory Day
• Varia (mostly outdated stuff)