School of Mathematical Sciences

EATCS Distinguished Dissertation Award menu

EATCS Distinguished Dissertation Award

We are delighted to announce that EPSRC-funded postdoc Heng Guo will receive a Distinguished Dissertation Award for his PhD thesis entitled “Complexity Classification of Exact and Approximate Counting Problems”. The award is sponsored by the European Association for Theoretical Computer Science (EATCS), which supports the interests of the subject in Europe.

Each year, a small number of PhD dissertations in the field of theoretical computer science are selected by a panel of experts for this distinction. The high standard of the achievement can be inferred from the fact that just three awards were made this year from a global field, not just from within Europe.

The thesis was undertaken at University of Wisconsin at Madison under the guidance of Professor Jin-Yi Cai. The counting problems of the title include weighted counting problems in the form of partition functions in statistical physics, and constraint satisfaction problems in artificial intelligence. It includes both positive results (efficient algorithms, either exact or approximate) and negative results (intractability relative to some complexity-theoretic assumption). A major achievement of the thesis is to get these two kinds of results to exactly complement each other in a wide range of situations, thus drawing an exact boundary between what is tractable and what is intractable. The thesis is notable in terms both of its wide scope and technical depth.

The award will be made the annual EATCS International Colloquium on Automata, Languages and Programming (ICALP) next month (July 2016). This colloquium in the premier meeting in theoretical computer science in Europe, and one of the top handful of conferences in the area worldwide.

Heng Guo's dissertation can be viewed here:
You can find out more about EATCS and the Award can be found here: