EATCS Distinguished Dissertation Award

The EATCS establishes the Distinguished Dissertation Award to promote and recognize outstanding dissertations in the field of Theoretical Computer Science.

Any PhD dissertation in the field of Theoretical Computer Science that has been successfully defended in 2023 is eligible.

Up to three dissertations will be selected by the committee for year 2023. The dissertations will be evaluated on the basis of originality and potential impact on their respective fields and on Theoretical Computer Science.

Each of the selected dissertations will receive a prize of 1000 Euro. The award receiving dissertations will be published on the EATCS web site, where all the EATCS Distinguished Dissertations will be collected.

The dissertation must be submitted by the author as an attachment to an email message sent to the address This e-mail address is being protected from spambots. You need JavaScript enabled to view it with subject EATCS Distinguished Dissertation Award 2023 by March 7th, 2024. The body of the message must specify:

  • Name and email address of the candidate;
  • Title of the dissertation;
  • Department that has awarded the PhD and denomination of the PhD program;
  • Name and email address of the thesis supervisor;
  • Date of the successful defence of the thesis.

A five page abstract of the dissertation and a letter by the thesis supervisor certifying that the thesis has been successfully defended must also be included. In addition, an endorsement letter from the thesis supervisor, and possibly one more endorsement letter, must be sent by the endorsers as attachments to an email message sent to the address This e-mail address is being protected from spambots. You need JavaScript enabled to view it with subject EATCS DDA 2023 endorsement. The name of the candidate should be clearly specified in the message.

The dissertations will be selected by the following committee:

  • Nikhil Bansal (chair)
  • Petra Berenbrink
  • Jaroslav Nešetřil
  • Damian Niwiński
  • Vladimiro Sassone
  • Alexandra Silva
  • David Woodruff
  • Standa Zivny

 

EATCS Distinguished Dissertation Award 2023 - Call for Nominations

The award committee will solicit the opinion of members of the research community as appropriate.

Theses supervised by members of the selection committee are not eligible.

The EATCS is committed to equal opportunities, and welcomes submissions of outstanding theses from all authors.

2024 / ICALP, Tallinn

  • William Kuszmaul: "Randomized Data Structures: New Perspectives and Hidden Surprises" (PhD at MIT; advisor: Charles E. Leiserson)
  • Nathan Klein: "Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems" (PhD at the University of Washington; advisors: Anna Karlin and Shayan Oveis Gharan), for his outstanding dissertation
  • Ruiwen Dong: "Algorithmic Problems for Subsemigroups of Infinite Groups" (PhD at the University of Oxford; advisors: Christoph Haase and James Worrell), for his outstanding dissertation

2023 / ICALP, Paderborn

  • Kuikui Liu: "Spectral Independence: A New Tool to Analyze Markov Chains" (University of Washington; supervisor: Shayan Oveis Gharan).
  • Alex Lombardi: "Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic" (Electrical Engineering and Computer Science (EECS) at MIT; supervisor: Vinod Vaikuntanathan)
  • Lijie Chen: "Better Hardness via Algorithms, and New Forms of Hardness versus Randomness" (MIT Department of Electrical Engineering and Computer Science; supervisor: Ryan Williams)

2022 / ICALP, Paris

  • Alexandros Hollender: "Structural Results for Total Search Complexity Classes with Applications to Game Theory and Optimisation (University of Oxford; advisor: Paul W. Goldberg)."
  • Jason Li: Preconditioning and Locality in Algorithm Design (Carnegie Mellon University; advisors: Anupam Gupta and Bernhard Haeupler).
  • Jan van den Brand: Dynamic Matrix Algorithms and Applications in Convex and Combinatorial Optimization (KTH Royal Institute of Technology; advisor: Danupon Nanongkai).

2021 / Glasgow, Scotland

  • Talya Eden: "Counting, Sampling and Testing Subgraphs in Sublinear-Time"
  • Marie Fortin: "Expressivity of first-order logic, star-free propositional dynamic logic and communicating automata"
  • Vera Traub: "Approximation Algorithms for Traveling Salesman Problems"

2020 / Saarbrücken, Germany

  • Josh Alman: "Linear Algebraic Techniques in Algorithms and Complexity"
  • Sándor Kisfaludi-Bak: " ETH-Tight Algorithms for Geometric Network Problems"
  • Jakub Tarnawski: "New Graph Algorithms via Polyhedral Techniques"

2019 / Patras, Greece

  • Arturs Backurs: "Below P vs NP: Fine-Grained Hardness for Big Data Problems"
  • Robert Robere: "Unified lower bounds for monotone computation"
  • Sepehr Assadi: "Combinatorial optimization on massive datasets: Streaming, Distributed, and massively parallel computation"

2018 / Prague, Czech Republic

  • Bas Ketsman: "Asynchronous Adventures: Formal Approaches to Querying Big Data in Shared-Nothing Systems"
  • Ilya Razenshteyn: "High-Dimensional Similarity Search and Sketching: Algorithms and Hardness"
  • Aviad Rubinstein: "Hardness of Approximation Between P and NP"

2017 / Warsaw, Poland

  • Vincent Cohen-Addad: "From Practice to Theory. Approximation schemes for clustering and network design"
  • Mika Göös: "Communication Lower Bounds via Query Complexity"
  • Steen Vester: "Game-based verification and synthesis"

2016 / Rome, Italy

2015 / Kyoto, Japan

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.