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


  1. Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
    Janardhan Kulkarni, Shi Li, Jakub Tarnawski and Minwei Ye
  2. 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
  3. A Constant-Factor Approximation Algorithm
    for the Asymmetric Traveling Salesman Problem

    Ola Svensson, Jakub Tarnawski and László Végh
  4. The Matching Problem in General Graphs is in Quasi-NC
    Ola Svensson and Jakub Tarnawski
  5. Streaming Robust Submodular Maximization:
    A Partitioned Thresholding Approach

    Slobodan Mitrović, Ilija Bogunović, Ashkan Norouzi-Fard, Jakub Tarnawski and Volkan Cevher
  6. Active Learning and Proofreading for Delineation of Curvilinear Structures
    Agata Mosińska, Jakub Tarnawski and Pascal Fua
  7. Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
    Christos Kalaitzis, Ola Svensson and Jakub Tarnawski
  8. Constant Factor Approximation for ATSP with Two Edge Weights
    Ola Svensson, Jakub Tarnawski and László Végh
  9. Fast Generation of Random Spanning Trees and the Effective Resistance Metric
    Aleksander Mądry, Damian Straszak and Jakub Tarnawski