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

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

Other

Non-science