Jakub Tarnawski

I am a doctoral student in the Theory of Computation laboratory at the EPFL, fortunate to have Ola Svensson as my advisor. I am broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms.

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