Krzysztof Onak

Shibulal Family Career Development Assistant Professor Faculty of Computing & Data Sciences Boston University Mailing address: Faculty of Computing & Data Sciences 665 Commonwealth Ave Boston, MA 02215 Office: CDS 1443 E-mail: krzysztof@onak.pl (personal, research) / konak@bu.edu (BU matters, research)

I am a Shibulal Family Career Development Assistant Professor in the Faculty of Computing & Data Sciences at Boston University.

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 have also contributed to many applied projects by designing and implementing efficient algorithms.

Before joining Boston University, I was a researcher at the IBM T.J. Watson Research Center, a Simons Postdoctoral Fellow at CMU, and a PhD student at MIT.

• Recent and current engagements:
  • 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)
  • STOC 2023 (PC member)
• Postdocs and students:
  • Esty Kelman (postdoc, co-hosted)
  • Dragos Ristache (PhD student)
  • Themistoklis Haris (PhD student)
  • Zi Song Yeoh (PhD student)
• Teaching:
  • Algorithmic Techniques for Taming Big Data (Spring 2025)
  • Algorithms for Data Science (Fall 2023)
  • Programming for Data Science (Spring 2022)
• CV (outdated)
• 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).
  
• 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).
  
• Parallel Algorithms for Geometric Graph Problems (with Alexandr Andoni, Aleksandar Nikolov, and Grigory Yaroslavtsev)
  The 46th ACM Symposium on Theory of Computing (STOC 2014).
• 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).
• Maintaining a Large Matching and a Small Vertex Cover (with Ronitt Rubinfeld)
  The 42nd ACM Symposium on Theory of Computing (STOC 2010).
  
• Constant-Time Approximation Algorithms via Local Improvements (with Huy N. Nguyen)
  The 49th Annual Symposium on Foundations of Computer Science (FOCS 2008).
  
• All publications
• Program committees: SOSA 2022, HALG 2021, ESA 2020, UAI 2020, UAI 2019, FSTTCS 2018, FOCS 2018, BeyondMR 2018, SODA 2018, BeyondMR 2017, BeyondMR 2016, STOC 2015, RANDOM 2014, SPIRE 2013, TAMC 2013, SODA 2013, ESA 2012 (Track A), MFCS 2011
• SUBLINEAR.INFO: a list of open problems in sublinear algorithms
• Varia (mostly outdated stuff)