Awards and Honors

Awards and Honors /Grants/Plenary Invited Lectures

  • Honorary Fellow of the Royal Society of New Zealand. Honorary Fellows include Einstein, Bohr, Curie, Darwin, Fleming, Priestley, Richter, Rutherford, altogether 230 since 1870.) (Awarded 2014)
  • Fellow of EATCS. One of the inaugural first ten EATCS Fellows, for “his role in founding the field of parameterized complexity theory, and for being a leader in computer science education.” (Awarded 2014)
  • EATCS–IPEC Nerode Prize. Awarded for a “series of papers that provide the mathematical framework establishing the field of kernelization algorithms as a rigorous theory having both upper and lower bounds. Altogether, these results and tools have paved the way for a disciplined and useful mathematical study of the major practical computing strategy of preprocessing.” (Awarded 2014)
  • International Gold Medal of Honor for Computer Science and Computer Science Education. ETH University of Zurich, for “Computer Science Unplugged! and sharing the foundations and open questions of computer science with students of all ages.” (Awarded January 2014)
  • Australia Prime Minister of Science Prize. short–listed (2014)
  • Australian Professorial Fellowship. Australian Research Council award for “outstanding researchers with proven international reputations to undertake research that is both of major importance in its field and of significant benefit to Australia.” (2010-2014)
  • My 60th birthday was a day of honor at Dagstuhl Seminar 12241: Data Reduction and Problem Kernels (2012). I was presented The Multivariate Algorithmic Revolution and Beyond, Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday (Springer, LNCS 7370, 2012). (Springer does not publish many festschrifts, so it is a signal honour.)
  • Honorary Professor, Royal Holloway, University of London (2009–ongoing).
  • Alexander von Humboldt Research Prize. This award provided a year-long research visit to Friedrich Schiller Univ, Jena with host Prof Dr. Rolf Niedermeier. During our time in Germany, split between two years, we visited many German research groups giving lectures, including MPI Saarbrucken, Lübeck, Aachen, Feiburg, Karlsruhe, Aachen, and others. (Awarded 2007 and taken in 2007 and 2008)
  • Fellow of the Institute of Advanced Study, Durham University. One of the inaugural Fellows, and Best Fellow of Grey College, giving public lectures as well as Institute presentations. (2006)
  • Fellowship to the Institute for the Study of Religion and Society, University of Victoria, British Columbia, Canada, for the study and development of religious passion plays about theoretical computer science (1998)
  • Erskine Fellowship. Department of Computer Science, University of Canterbury, NZ. (1996)

My research has been supported by the following research funding agencies

U.S. Sandia Laboratories (1), U.S. National Science Foundation (2), U.S. Office of Naval Research (3), U.S. National Aeronautics and Space (1), U.S. Dept of Energy (1), Canada NSERC (8), Canada PIMS (1), British Columbia Ministry of Training and Development (1), New Zealand Marsden Fund (1), Victoria Univ Wellington, NZ (2), Univ Newcastle, AU (1), Australian Research Council Discovery Grant (6), Australian Professorial Fellowship (1), Alexander von Humboldt Research Prize (1).

Invited presentations to internationally established conferences and advanced schools. I am invited to chair Open Problem Sessions and be Speaker at most Parameterized Complexity workshops/conf/schools: more invitations than I can accept. I am plenary speaker at 3 – 5 events annually, including the following.

2015 Games and Cognition Workshop @SMARTCogSci Amsterdam (March); Lecture Series Univ Hong Kong (July); Conf on Topics in Theoretical Computer Science, Tehran (August)

2014 Latin American Workshop on Cliques in Graphs, Brazil (Nov); Dagstuhl Seminar 14341 Resource Bounded Problem-Solving (Cognitive Neuroscience) (Aug); 2nd Workshop on Parameterized Complexity of Computational Reasoning, part of FLoC 2014, Vienna (July); CodeWeek Europe Expert Panel, Vienna (July); Toward the Ground Truth, Exact Algorithms for Bioinformatics Research, Shonan (March).

2013 Distinguished Lecture in the Distinguished Lecture Series at Univ California, San Diego (Dec); Laudation in honor of Anil Nerode’s 80th birthday at a special session of Logical Foundations of Computer Science at AMS Annual Meeting, San Diego, organized by Prof. Sergei Artemov (Jan); 6th Workshop on Graph Classes, Optimization, and Width Parameters, Santorini (Aug); Alexander von Humboldt colloquia “Looking to the Future: International Research in a Changing World,” Sydney (Oct).

2012 Short courses: Nanyang Univ Technology, Singapore (Jan); German Technical Univ of Oman (Jan); Institute for Mathematical Sciences, Chennai (Jan); CATS, Melbourne (Feb); Technion, Haifa (March-April); Lebanese American Univ, Beirut (April). Laudation at “Bruno-Fest” honoring Prof Bruno Courcelle, Univ of Bordeaux (June); Asian Logic Conf Special Session on Logical Aspects of Graphs and Matroids, Wellington NZ; Applications of Parameterized Algorithms and Complexity (APAC), co-located with ICALP Phylomania Conference, Hobart, Tasmania (Nov); KPVY Vijyoshi Science Camp for talented science students. About 600 students attend. Indian Institute of Science Bangalore (Dec). Keynotes are Nobel Laureates and distinguished scientists. The KPVY Convener says, “The quality of these kids is so good…I consider this programme to be of vital importance for the future of science.”

Earlier DIMAP,FAW/AAIM, IWOCA,WorKer, Algebraic, Topological and Complexity Aspects of Graph Covers Workshop, Auckland (Feb 2010); Computational Social Choice, Auckland (Feb 2010); Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, Canberra (Dec 2010).

Professional Contributions

Editorships / Program Organization and Committees / Student Supervision

Editorships

Associate Editor of the Journal of Computer and System Sciences

Associate Editor of the ACM Transactions on Algorithms

Guest Editor (with F. Fomin and G. Gutin) of Special Issue “Parameterized Complexity of Discrete Optimization” of the journal Discrete Optimization, 2011.

Guest Editor (with R. Downey and M. Langston) of double special issue of The Computer Journal (Volumes 1 and 3) with 17 survey papers on various areas of parameterized algorithms and complexity, 2008.

Review Panel for the Institute of Mathematical Sciences, Chennai. One of three theoretical computer scientists from outside India invited to serve, 2009. Reviewer for fifteen national science agencies.

Alexander von Humboldt Representative for the Northern Territory, Australia

Symposium/Conference/Workshop organization (star indicates inauguration of new series)

  • First Idaho Office of Naval Research Workshop on Software Research, Conference Chair, June 1989.
  • Second Idaho Office of Naval Research Workshop on Software Research, Conference Chair, June 1990.
  • STOC ’92 Victoria, BC, Canada. Conference Chair, May 1992.

★ I co-organized the first Dagstuhl seminar in the field, Seminar 01311: Parameterized Complexity, with Rod Downey, Rolf Niedermeier, Peter Rossmanith, August 2001. There have been 22 related seminars since then. I have officially co-organized Seminar 03311: Fixed Parameterized Algorithms, Co-organizers Michael Hallett, Naomi Nishimura, Rolf Niedermeier, July 2003 and Seminar 12241: Data Reduction and Problem Kernels, Co-organizers Jiong Guo, Dániel Marx, Saket Saurabh, June 2012, and unofficially assisted with many others.

★ The International Symposium on Parameterized and Exact Computation series (IWPEC and later IPEC) was planned with a precursor workshop at IMSc Chennai, Co-organized with Venkatesh Raman and Frances Rosamond, 2000. Rod Downey and I Co-chaired the first IWPEC, part of ALGO, Bergen in 2004. The tenth IPEC will take place in 2015, also part of ALGO. I have been on the Steering or Program Committee for most of the series.

  • Workshop on Structural Aspects of Parameterized Complexity, in conjunction with FST-TCS 2002, Kanpur, India, Co-organizer Venkatesh Raman, December 2002.
  • Using Parameterized Complexity Analysis in Cognitive Science, workshop with Iris van Rooij, Moritz Muller, Frances Rosamond, Amsterdam 2010.

Parameterized Complexity: Not-About-Graphs Workshop series was inaugurated in Darwin, Australia with Frances Rosamond, 2011. Workshops have been held at the German Technical University, Oman, Co-chair Rudolf Fleischer, August 2013 and at IMSC, Chennai, Co-chair Saket Saurabh, Dec 2014.

  • Parameterized Complexity – Multivariate Complexity Analysis Tutorial at the Computing: Australasian Theory Symposium: CATS (ACSW Week), Chair, Melbourne 2012.

Applications of Parameterized Algorithms and Complexity with G. Gutin, co-located ICALP, July 2012.

  • AMS Special Session: Mathematical Underpinnings of Multivariate Complexity Theory and Algorithm Design, Frontiers and the Field of Incrementalization, with R. Downey, Nerode, F. Rosamond, 2013.
  • 2nd Workshop on Parameterized Complexity of Computational Reasoning PCCR), part of FLoC 2014, Vienna, Co-organizer with Stefan Szeider, Serge Gaspers, July 2014.
  • Bertinoro Workshop: Frontiers and Connections between Parametrization and Approximation, Co-organizers Hadas Shachnai, Klaus Jansen, Vangelis Paschos, May 2014.
  • BIRS Institute 15w5118: Approximation Algorithms and Parameterized Complexity, Co-organizers H. Shachnai, K. Jansen, R. Solis-Oba, Banff, November 2015.

Program Committees

DMTCS 2002, FST-TCS 2002, COCOON 2003, WADS 2003, CATS 2003, ACSW 2003, CATS 2004, ACSW 2004, WG 2004, IWPEC 2004 (Co-Chair), MFCS 2005, ACSW 2005, IWPEC 2006, WG 2008, COCOA 2008, FAW 2008, ICYCS 2008 (Co-Chair), ALENEX 2009, IWPEC 2009, TAMC 2009, FAW 2009, COMSOC 2010, IWOCA 2010, LATA 2010, IPEC 2010, TAMC 2012, APEX 2012, MFCS 2012, FAW-AAIM 2013 (Co-Chair), LATA 2013, APEX 2013, IPEC 2013, LATA 2014, AAIM 2014.

PhD supervision

PhD students: Mark Hoover (1989, Educational Testing Services), Yasu Koda (1991, industry), Xiuyan Liu (1994, industry), Michael Dinneen (1996, Sr. Lecturer at Univ Auckland), Michael Hallett (1996, Director, McGill Medical Ctr), Todd Wareham (1997, Assoc Prof Memorial Univ, Canada), Patricia Evans (1999. Prof Univ New Brunswick, Canada), Elena Prieto-Rodriguez (2005, Lecturer at Univ Newcastle, Australia), Peter Shaw (2006, Sr. Lecturer, Charles Darwin Univ, Au). Postdocs: Ulrike Stege (now Assoc Prof at Univ Victoria, BC, Canada), Iris van Rooij (Director, Computational Cognitive Science group at Donders Institute for Brain, Cognition and Behaviour, Univ Nijmegen), Mahdi Parsa (Researcher, Univ Strathclyde, UK).

Contribution to the early careers of excellent researchers. I (and my wife Frances, who edits the Parameterized Complexity Newsletter) take pleasure in mentoring young researchers into the field of parameterized complexity, often with lengthy visits to our home in Australia. Some of these visitors have received major academic awards, including three with ERC Starting Grants, one with a similar Australian award.

  • Daniel Marx has a ten-year record of over 2000 citations (h=26, g=40).
  • Saket Saurabh has a ten-year record of over 1700 citations (h=27, g=38).
  • Stefan Szeider has a ten-year record of over 1600 citations (h=20, g=30).
  • Danny Hermelin has a ten-year record of over 1100 citations (h=14, g=31).
  • Serge Gaspers has a ten-year record of over 700 citations (h=13, g=31).

In addition to those mentioned above, and more still in earlier career stages, the list includes Bart Jansen, Matthias Mnich and Gabor Erdelyi, all of whom have become committed scientists, and won prizes, including in some cases, permanent academic positions. Frances and I have had “non-standard” academic career paths since 2004. We have been compared to Paul Erdös in that regard. For nearly ten years we had no permanent abode — we spend about half of every year on international PC community-building expeditions, and the other half in Australia, with more-or-less nonstop hosting of young research visitors, often several at a time.

Parameterised Complexity