Presburger Award 2021 – Laudatio for Shayan Oveis GharanThe 2021 Presburger Award Committee has unanimously selected Shayan Oveis Gharan as the recipient of the 2021 EATCS Presburger Award for Young Scientists for his creative, profound, and ambitious contributions to the Traveling Salesman problem. Traveling Salesman is a drosophilia of theoretical computer science: immediately accessible, intellectually appealing, computationally difficult, and extremely well-studied. It serves as a milestone and showcase for progress in our scientific understanding of the design and analysis of algorithms. Oveis Gharan's work began during his PhD thesis, in a paper that presents an asymptotically sublogarithmic approximation guarantee for the Traveling Salesman problem for the general (or, “asymmetric”) case. The primary tool is the negative dependence between the presence of edges in a certain distribution on random spanning trees of a graph, a theme that has matured and expanded throughout much of the recipient’s work. In a remarkable tour de force, Oveis Gharan and his coauthors followed this up with a (3/2–ε)- approximation for the symmetric graphic case, and later also for the metric case. These results rely on a deeper understanding of negative dependence through the lens of strongly Rayleigh measures and real-stable polynomials, the polyhedral structure of the Held–Karp polytope, and the combinatorics of near-minimum cuts in a graph. Besides his work on TSP, Oveis Gharan exhibits an amazingly consistent ability to make progress on many other problems that had remained opened for decades. For example, a Cheeger inequality proved by Oveis Gharan and co-authors was the main technical tool in Miclo’s proof of a 40-year old conjecture of Simon and Høegh-Krohn in the field of mathematical physics. The interplay between analysis, probability, and combinatorics is a hallmark of his research programme and a sterling example of how questions arising from theoretical computer science lead to profound progress in related fields.
Presburger Award Committee 2021 Mikołaj Bojańczyk Thore Husfeldt (chair) Meena Mahajan
The Presburger Award is awarded by the European Association for Theoretical Computer Science (EATCS) to a young scientist for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The award is named after Mojżesz Presburger who accomplished his path-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929. The list of the previous recipients of the Presburger Award is available at http://eatcs.org/index.php/presburger |
