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

Sep 2022 Differentially private correlation clustering accepted to NeurIPS
Jun 2022 New Harmony work on DNN training accepted to VLDB
May 2022 Again serving on the Scientific Committee (problemsetting) of EGOI (European Girls' Olympiad in Informatics)
Mar 2022 Excited to work with June Vuong and Shyam Narayanan as interns at MSR this summer
Feb 2022 1.6-competitive algorithm for online edge coloring accepted to STOC 2022
Oct 2021 Work on scheduling with communication delays hardness accepted to SODA 2022
Sep 2021 Piper (DNN training parallelism optimizer) accepted to NeurIPS 2021
Jul 2021 Honored to receive the 2021 Tucker Prize
Jun 2021 Serving on the Scientific Committee (problemsetting) of the first EGOI (European Girls' Olympiad in Informatics)
Jun 2021 Excited to work with Yang P. Liu and Mehtaab Sawhney as interns at MSR this summer
May 2021 Our work on correlation clustering was accepted to ICML 2021 as a long talk
Oct 2020 Honored to receive the EPFL Doctorate Award 2020
Sep 2020 Honored to receive the GI-Dissertationspreis
Sep 2020 Follow-up work on scheduling with communication delays accepted to SODA 2021
Sep 2020 Three papers accepted to NeurIPS 2020 (dynamic submodular as oral)
Jul 2020 Honored to receive the ACM Dissertation Award Honorable Mention
Jul 2020 Our work on scheduling with communication delays was accepted to FOCS 2020
Jun 2020 Excited to have Sami Davies, Nathan Klein and Jason Li as interns at MSR this summer
May 2020 Happy to serve on the Program Committee of APPROX 2020
Apr 2020 Honored to receive the EATCS Dissertation Award

Publications

  1. Near-Optimal Correlation Clustering with Privacy
    Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis and Jakub Tarnawski
  2. 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
  3. Online Edge Coloring via Tree Recurrences and Correlation Decay
    Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney and Jakub Tarnawski
  4. Piper: Multidimensional Planner for DNN Parallelization
    Jakub Tarnawski, Deepak Narayanan and Amar Phanishayee
  5. On the Hardness of Scheduling With Non-Uniform Communication Delays
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski and Yihao Zhang
  6. Correlation Clustering in Constant Many Parallel Rounds
    Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Nikos Parotsidis and Jakub Tarnawski
  7. 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
  8. Fully Dynamic Algorithm for Constrained Submodular Optimization
    Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub Tarnawski and Morteza Zadimoghaddam
  9. Fairness in Streaming Submodular Maximization: Algorithms and Hardness
    Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos and Jakub Tarnawski
  10. Efficient Algorithms for Device Placement of DNN Graph Operators
    Jakub Tarnawski, Amar Phanishayee, Nikhil R. Devanur, Divya Mahajan and Fanny Nina Paravecino
  11. Scheduling with Communication Delays via LP Hierarchies and Clustering
    Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski and Yihao Zhang
  12. Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
    Janardhan Kulkarni, Shi Li, Jakub Tarnawski and Minwei Ye
  13. Recent Results on the Traveling Salesman Problem
    Jakub Tarnawski and Vera Traub
  14. 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
  15. A Constant-Factor Approximation Algorithm
    for the Asymmetric Traveling Salesman Problem
    Ola Svensson, Jakub Tarnawski and László Végh
  16. The Matching Problem in General Graphs is in Quasi-NC
    Ola Svensson and Jakub Tarnawski
  17. Streaming Robust Submodular Maximization:
    A Partitioned Thresholding Approach
    Slobodan Mitrović, Ilija Bogunović, Ashkan Norouzi-Fard, Jakub Tarnawski and Volkan Cevher
  18. Active Learning and Proofreading for Delineation of Curvilinear Structures
    Agata Mosińska, Jakub Tarnawski and Pascal Fua
  19. Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
    Christos Kalaitzis, Ola Svensson and Jakub Tarnawski
  20. Constant Factor Approximation for ATSP with Two Edge Weights
    Ola Svensson, Jakub Tarnawski and László Végh
  21. Fast Generation of Random Spanning Trees and the Effective Resistance Metric
    Aleksander Mądry, Damian Straszak and Jakub Tarnawski

Other

Non-science