The EATCS Award 2020 - Laudatio for Mihalis Yannakakis

The EATCS Award committee selects

Professor Mihalis Yannakakis

as the recipient of the 2020 EATCS Award for his fundamental and deep contributions to an extraordinary range of areas in theoretical computer science, including algorithms, complexity theory, combinatorial optimization, databases, and verification.


A small sampling of Yannakakis's many celebrated contributions include:

  • groundbreaking work, decades ahead of its time, on the power and limitations of linear programming (symmetric) extended formulations for solving combinatorial optimization problems;
  • seminal work on hardness of approximation, introduction of max-SNP, and establishing key hardness results in the PCP theory for fundamental problems including graph coloring and set cover;
  • pioneering work on the complexity of local search, the definition of the complexity class PLS, and proofs of PLS-completeness for several fundamental local search problems;
  • many trailblazing works in database theory, including introduction of acyclic database schemes, and establishing a polynomial time algorithm for evaluating acyclic conjunctive queries over relational databases;
  • fundamental work in the algorithmic theory of automated verification and testing, including novel efficient algorithms for model checking temporal properties of probabilistic systems.


In summary, Yannakakis's astounding body of work has profoundly enriched theoretical computer science, and it continues to have a lasting impact and inspires much ongoing research in all these fields. your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.