Professional Contributions

Professional Contributions

Editorships / Program Organization and Committees / Student Supervision


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