Professor Martin Dyer awarded the Godel Prize 2021
Professor Martin Dyer wins the Godel Prize 2021 Prize for outstanding papers in the area of theoretical computer science
Professor Martin Dyer’s paper, for which he was the lead author, An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Computing. 42(3): 1245-1274 (2013) has been awarded the Godel Prize 2021.
Professor Martin Dyer is part of the Algorithms & Complexities Research Theme in the School of Computing. His current research interests are algorithms and computing theory, in particular randomized algorithms, algorithms and complexity and algorithms for geometric problems. He is also interested in parallel computing and problems in computational biology.
His paper above is part of a culmination of a large body of work on the classification of counting complexity of CSPs and prove an all-encompassing Complexity Dichotomy Theorem for counting CSP-type problems that are expressible as a partition function.
Sponsored jointly by the European Association of Theoretical Computer Science and ACM SIGACT, the prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before Neumann's death, in what has become the famous "P versus NP" question. The Prize includes an award of $5000 (US) and is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC); this year it will be presented at STOC.
More information can be seen at: https://eatcs.org/index.php/component/content/article/1-news/2885-2021-05-07-21-20-13
