Computing article selected as one of world's best

An article coauthored by Dr Olaf Beyersdorff from the Algorithms and Complexity Group, School of Computing has been selected by ACM Computing Reviews.

It has been selected as one of the best papers in computing published worldwide in 2012. Dr Beyersdorff's article,Parameterized bounded-depth Frege is not optimal, was chosen as one of 11 papers from Theory of Computing.

The listing as a Notable Computing Article recognises an important contribution to proof complexity, an area of theoretical computer science analysing the difficulty of proving mathematical theorems. The paper demonstrates a striking lower bound for the proof size of the famous pigeonhole principle in parameterized bounded-depth Frege. The research is joint work with Nicola Galesi (Rome), Massimo Lauria (Stockholm) and Nevanlinna and Gödel prize winner Alexander Razborov (Chicago).

Further information

Find the paper in full in the ACM Digital Library - Parameterized bounded-depth Frege is not optimal