photo

Jakub Tarnawski

I am a researcher at Microsoft Research. I am broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms.

I completed my PhD in Computer Science in 2019 at EPFL, where I was fortunate to have Ola Svensson as my advisor. I received my MSc in Mathematics and Computer Science from the University of Wrocław, Poland.

Email firstname.lastname at microsoft.com
Pronouns he/his

News

Oct 2025 Sublinear algorithm for Steiner Forest and MIS accepted to SODA
Sep 2025 Work on fair matroid submodular maximization accepted to NeurIPS
Apr 2025 Work on sublinear matching accepted to ICALP
Mar 2025 Excited to work with Yaowei Long and Prasanna Ramakrishnan as interns at MSR this summer
Nov 2024 Work on sublinear Steiner tree accepted to ITCS
Oct 2024 Serving on the Program Committee of STACS 2025
May 2024 Phaze (architecture search with device placement and op scheduling) accepted to ICML
May 2024 DéjàVu (KV-caching to accelerate LLM serving) accepted to ICML
Jan 2024 Work on private sums of kernel/distance functions accepted to ICLR
Jan 2024 Work on fair matroid submodular maximization accepted to AISTATS
Jul 2023 Honored to receive the Frontiers of Science Award at the International Congress of Basic Science for the ATSP work
Apr 2023 Work on streaming fair matroid submodular maximization accepted to ICML
Jan 2023 Again serving on the Scientific Committee (problemsetting) of EGOI (European Girls' Olympiad in Informatics)

Publications

  1. Sublinear Metric Steiner Forest via Maximal Independent Set
    Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski and Ali Vakilian
  2. Improved Algorithms for Fair Matroid Submodular Maximization
    Sepideh Mahabadi, Sherry Sarkar and Jakub Tarnawski
  3. A 0.51-Approximation of Maximum Matching in Sublinear n1.5 Time
    Sepideh Mahabadi, Mohammad Roghani and Jakub Tarnawski
  4. Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
    Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski and Ali Vakilian
  5. Integrated Hardware Architecture and Device Placement Search (Phaze)
    Irene Wang, Jakub Tarnawski, Amar Phanishayee and Divya Mahajan
  6. DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving
    Foteini Strati, Sara McAllister, Amar Phanishayee, Jakub Tarnawski and Ana Klimović
  7. Efficiently Computing Similarities to Private Datasets
    Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal and Jakub Tarnawski
  8. Fairness in Submodular Maximization over a Matroid Constraint
    Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard and Thuy-Duong Vuong
  9. Fairness in Streaming Submodular Maximization over a Matroid Constraint
    Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos and Jakub Tarnawski
  10. Near-Optimal Correlation Clustering with Privacy
    Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis and Jakub Tarnawski
  11. Harmony: Overcoming the hurdles of GPU memory capacity to train massive DNN models on commodity servers
    Youjie Li, Amar Phanishayee, Derek Murray, Jakub Tarnawski and Nam Sung Kim
  12. Online Edge Coloring via Tree Recurrences and Correlation Decay
    Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney and Jakub Tarnawski
  13. Piper: Multidimensional Planner for DNN Parallelization
    Jakub Tarnawski, Deepak Narayanan and Amar Phanishayee
  14. On the Hardness of Scheduling With Non-Uniform Communication Delays
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski and Yihao Zhang
  15. Correlation Clustering in Constant Many Parallel Rounds
    Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis and Jakub Tarnawski
  16. Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski and Yihao Zhang
  17. Fully Dynamic Algorithm for Constrained Submodular Optimization
    Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub Tarnawski and Morteza Zadimoghaddam
  18. Fairness in Streaming Submodular Maximization: Algorithms and Hardness
    Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos and Jakub Tarnawski
  19. Efficient Algorithms for Device Placement of DNN Graph Operators
    Jakub Tarnawski, Amar Phanishayee, Nikhil R. Devanur, Divya Mahajan and Fanny Nina Paravecino
  20. Scheduling with Communication Delays via LP Hierarchies and Clustering
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski and Yihao Zhang
  21. Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
    Janardhan Kulkarni, Shi Li, Jakub Tarnawski and Minwei Ye
  22. Recent Results on the Traveling Salesman Problem
    Jakub Tarnawski and Vera Traub
  23. Beyond 1/2-Approximation for Submodular Maximization
    on Massive Data Streams
    Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović, Amir Zandieh, Aida Mousavifar and Ola Svensson
  24. A Constant-Factor Approximation Algorithm
    for the Asymmetric Traveling Salesman Problem
    Ola Svensson, Jakub Tarnawski and László Végh
  25. The Matching Problem in General Graphs is in Quasi-NC
    Ola Svensson and Jakub Tarnawski
  26. Streaming Robust Submodular Maximization:
    A Partitioned Thresholding Approach
    Slobodan Mitrović, Ilija Bogunović, Ashkan Norouzi-Fard, Jakub Tarnawski and Volkan Cevher
  27. Active Learning and Proofreading for Delineation of Curvilinear Structures
    Agata Mosińska, Jakub Tarnawski and Pascal Fua
  28. Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
    Christos Kalaitzis, Ola Svensson and Jakub Tarnawski
  29. Constant Factor Approximation for ATSP with Two Edge Weights
    Ola Svensson, Jakub Tarnawski and László Végh
  30. Fast Generation of Random Spanning Trees and the Effective Resistance Metric
    Aleksander Mądry, Damian Straszak and Jakub Tarnawski

Other

Non-science