Thursday, March 25, 2010

LICS 2010 Accepted Papers and Martin Grohe's Latest Opus

The list of accepted papers for LICS 2010 is out. As usual, the programme looks very interesting and exceedingly strong.

For an interested, but not very knowledgeable, observer like me, one of the most interesting looking papers that have been selected for the conference seems to be yet another seminal contribution by Martin Grohe. The paper is Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors.

From the abstract of that ten-page paper, I learn that Grohe proves that fixed-point logic with counting captures polynomial time over all classes of graphs with excluded minors. To my untrained eye, this looks like an amazing result. The proof of this theorem will take up the whole of this monograph, which is currently being written and will be well over 200 pages long. The current draft spans 238 pages.

Would such a result meet the current requirements for the Gödel prize, say? It seems to me that it would not, unless Grohe also publishes a journal paper based on a fragment of his monograph. Taking the view that proofs of certain results are likely to be very long and that very few journals in computer science would publish papers that are 250 pages long, say, would it not be reasonable to let a research monograph qualify a piece of research for the Gödel prize? After all, if the result is important, it will be studied in depth by many researchers, ensuring a more thorough level of peer review than the one obtained via a standard refereeing process for a journal.

1 comment:

Chandra said...

Thanks for the pointer to this new work.