Jakub Tarnawski

I am an algorithms 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 the 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
INJ 110, Station 14
CH-1015 Lausanne
Office INJ 110


  1. Beyond 1/2-Approximation for Submodular Maximization
    on Massive Data Streams

    A. Norouzi Fard, J. Tarnawski, S. Mitrović, A. Zandieh, A. Mousavifar and O. Svensson
  2. A Constant-Factor Approximation Algorithm
    for the Asymmetric Traveling Salesman Problem

    O. Svensson, J. Tarnawski and L. Végh
  3. The Matching Problem in General Graphs is in Quasi-NC
    O. Svensson and J. Tarnawski
  4. Streaming Robust Submodular Maximization:
    A Partitioned Thresholding Approach

    S. Mitrović, I. Bogunović, A. Norouzi Fard, J. Tarnawski and V. Cevher
  5. Active Learning and Proofreading for Delineation of Curvilinear Structures
    A. Mosińska, J. Tarnawski and P. Fua
  6. Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios
    C. Kalaitzis, O. Svensson and J. Tarnawski
  7. Constant Factor Approximation for ATSP with Two Edge Weights
    O. Svensson, J. Tarnawski and L. Végh
  8. Fast Generation of Random Spanning Trees and the Effective Resistance Metric
    A. Mądry, D. Straszak and J. Tarnawski