Jakub Tarnawski receives Honorable Mention in 2019 ACM Awards

Tarnawski, who is now a computer science researcher for Microsoft Research, initially completed a Masters in Mathematics and Computer Science at the University of Wrocław. He then moved to Lausanne for his PhD studies at the EPFL School of Computer and Communication Sciences (IC) where he worked on graph and approximation algorithms, classic branches of theoretical computer science that have a number of important applications in network analysis in biology, chemistry, operations research, engineering and even sociology.

ACM is the world’s largest educational and scientific computing society. Each year they recognise research excellence by presenting both an annual award and honourable mention awards to the best doctoral dissertations in computer science and engineering. Tarnawski’s achievement marks the first time an EPFL student has received an honourable mention from ACM since 2005.

Tackling unsolved questions in graph theory

Tarnawski’s dissertation New Graph Algorithms via Polyhedral Techniqueswas described by ACM as having made ‘groundbreaking algorithmic progress’ on the so-called matching and travelling salesman optimization problems, categories of graph theory which have intrigued mathematicians since they were first devised in the 1800s. 

Since the 1950s, computer scientists have been attempting to find the best methods of solving these problems. Many of the suggested solutions have been used to reduce production costs in manufacturing, and more recently in medical image processing. Tarnawski’s work went some way towards resolving several important questions in this field which scientists have been attempting to tackle for more than half a century.

One part of his dissertation attempted to determine whether randomness is required to obtain fast parallel matching algorithms, a question which had long been regarded as an unsolved mystery in computer science. His work was described as having made significant progress in this regard, through the process of almost completely derandomizing a three-decade-old randomized parallel matching algorithm.

The dissertation also built on the work of pioneering Stanford computer scientist George Dantzig in the 1950s, solved a special instance of the travelling salesman problem – the question of finding the shortest tour of n given cities – using a linear program. Tarnawski was able to make progress in the analysis of the strength of that linear program, and develop the first constant-factor approximation algorithm for the more complex asymmetric version of the traveling salesman problem.

“I have many fond memories from Jakub’s time as a PhD student,” said Ola Svensson, EPFL’s doctoral program director. “The years 2017-2018 were especially magic with several amazing results including those cited in the press release. I feel fortunate to have been his advisor and I am very happy that he has received this prestigious honourable mention.”

Tarnawski will receive $5,000 when the awards are formally recognized at the annual ACM Awards Banquet on October 3 in San Francisco.