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

Jan 2024 Work on private sums of kernel/distance functions accepted to ICLR
Jan 2024 Work on fair matroid submodular maximization accepted to AISTATS
Oct 2023 Our group at MSR Redmond is looking for theory and ML interns for 2024
Jul 2023 Honored to receive the Frontiers of Science Award at the International Congress of Basic Science for the ATSP work
Jul 2023 Excited to work with Sandeep Silwal as intern at MSR this summer
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. Efficiently Computing Similarities to Private Datasets
    Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal and Jakub Tarnawski
  2. Fairness in Submodular Maximization over a Matroid Constraint
    Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard and Thuy-Duong Vuong
  3. DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving
  4. Fairness in Streaming Submodular Maximization over a Matroid Constraint
    Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos and Jakub Tarnawski
  5. Near-Optimal Correlation Clustering with Privacy
    Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis and Jakub Tarnawski
  6. 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
  7. Online Edge Coloring via Tree Recurrences and Correlation Decay
    Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney and Jakub Tarnawski
  8. Piper: Multidimensional Planner for DNN Parallelization
    Jakub Tarnawski, Deepak Narayanan and Amar Phanishayee
  9. On the Hardness of Scheduling With Non-Uniform Communication Delays
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski and Yihao Zhang
  10. Correlation Clustering in Constant Many Parallel Rounds
    Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis and Jakub Tarnawski
  11. 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
  12. Fully Dynamic Algorithm for Constrained Submodular Optimization
    Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub Tarnawski and Morteza Zadimoghaddam
  13. Fairness in Streaming Submodular Maximization: Algorithms and Hardness
    Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos and Jakub Tarnawski
  14. Efficient Algorithms for Device Placement of DNN Graph Operators
    Jakub Tarnawski, Amar Phanishayee, Nikhil R. Devanur, Divya Mahajan and Fanny Nina Paravecino
  15. Scheduling with Communication Delays via LP Hierarchies and Clustering
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski and Yihao Zhang
  16. Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
    Janardhan Kulkarni, Shi Li, Jakub Tarnawski and Minwei Ye
  17. Recent Results on the Traveling Salesman Problem
    Jakub Tarnawski and Vera Traub
  18. 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
  19. A Constant-Factor Approximation Algorithm
    for the Asymmetric Traveling Salesman Problem
    Ola Svensson, Jakub Tarnawski and László Végh
  20. The Matching Problem in General Graphs is in Quasi-NC
    Ola Svensson and Jakub Tarnawski
  21. Streaming Robust Submodular Maximization:
    A Partitioned Thresholding Approach
    Slobodan Mitrović, Ilija Bogunović, Ashkan Norouzi-Fard, Jakub Tarnawski and Volkan Cevher
  22. Active Learning and Proofreading for Delineation of Curvilinear Structures
    Agata Mosińska, Jakub Tarnawski and Pascal Fua
  23. Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
    Christos Kalaitzis, Ola Svensson and Jakub Tarnawski
  24. Constant Factor Approximation for ATSP with Two Edge Weights
    Ola Svensson, Jakub Tarnawski and László Végh
  25. Fast Generation of Random Spanning Trees and the Effective Resistance Metric
    Aleksander Mądry, Damian Straszak and Jakub Tarnawski

Other

Non-science