Charles Darwin University
enews home

Academic wins international maths prize

By Patrick Nelson

Professor Mike Fellows … Nerode Prize winner Professor Mike Fellows … Nerode Prize winner

CDU computer scientist Professor Mike Fellows has been named among the winners of an international mathematics prize presented in Europe recently.

Professor Fellows was one of four co-authors to be declared joint winners of the European Association for Theoretical Computer Science’s Nerode Prize at the International Seminar on Parameterized and Exact Computation in Poland.

Their paper, “On problems without polynomial kernels” and a second paper by two other authors were regarded by the prize committee as containing outstanding research in the area of multivariate algorithmics.

The judges wrote: “Their two papers provide the mathematical framework establishing the field of kernelization algorithms as a rigorous theory having both upper and lower bounds.

“The first paper (co-written by Professor Fellows) introduces the key notions to make this connection, in the form of a distillation algorithm for classical problems and of a composition algorithm for parameterized problems.

“(Collectively they) … have paved the way for a disciplined and useful mathematical study of the major practical computing strategy of pre-processing.”

Both papers were published in the Journal of Computer and System Sciences: They were:
“On problems without polynomial kernels” by Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin. “Infeasibility of instance compression and succinct PCPs for NP” by Lance Fortnow, Rahul Santhanam.