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

Nov 2024 Our group at MSR Redmond is looking for interns in theory as well as ML for spring/summer 2025
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
Apr 2024 Excited to work with Mohammad Roghani and Sherry Sarkar as interns at MSR this summer
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)
Sep 2022 Differentially private correlation clustering accepted to NeurIPS
Jun 2022 New Harmony work on DNN training accepted to VLDB
Feb 2022 1.6-competitive algorithm for online edge coloring accepted to STOC

Publications

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

Other

Non-science