Rodney Graham Downey (born 20 September 1957) is an Australian and New Zealand mathematician and computer scientist, a professor in the School of Mathematics, Statistics and Operations Research at Victoria University of Wellington in New Zealand. He is known for his work in mathematical logic and computational complexity theory, and in particular for founding the field of parameterized complexity together with Michael Fellows.
Downey earned a bachelor's degree at the University of Queensland in 1978, and then went on to graduate school at Monash University, earning a doctorate in 1982 under the supervision of John Crossley. After holding teaching and visiting positions at the Chisholm Institute of Technology, Western Illinois University, the National University of Singapore, and the University of Illinois at Urbana-Champaign, he came to New Zealand in 1986 as a lecturer at Victoria University. He was promoted to reader in 1991, and was given a personal chair at Victoria in 1995.
Downey is the co-author of two books:
- Parameterized Complexity (with Michael Fellows, Springer, 1999)
- Algorithmic Randomness and Complexity (with D. Hirschfeldt, Springer, 2010)
He is also the author or co-author of over 200 research papers, including a highly cited sequence of four papers with Michael Fellows and Karl Abrahamson setting the foundation for the study of parameterized complexity.
Awards and honours
In 1992 Downey won the Research Award of the New Zealand Mathematical Society "for penetrating and prolific investigations that have made him a leading expert in many aspects of recursion theory, effective algebra and complexity". He became a fellow of the Royal Society of New Zealand in 1996. He was elected as an ACM Fellow in 2007 "for contributions to computability and complexity theory", becoming the second ACM Fellow in New Zealand, and in the same year was elected as a fellow of the New Zealand Mathematical Society. In 2010 he won the Shoenfield Prize of the Association for Symbolic Logic for his work with Denis Hirschfeldt, Andrew Nies, and Sebastiaan Terwijn on randomness. In 2011 the Royal Society of New Zealand gave him their Hector Medal "for his outstanding, internationally acclaimed work in recursion theory, computational complexity, and other aspects of mathematical logic and combinatorics." In 2012 he became a fellow of the American Mathematical Society.
- Curriculum vitae, retrieved 2012-02-19.
- Whittle, Geoff (August 2004), "Centrefold: Rod Downey", Newsletter of the New Zealand Mathematical Society 91.
- Faculty profile, Victoria University of Wellington, retrieved 2012-02-19.
- Rodney Graham Downey at the Mathematics Genealogy Project
- Downey, Rod (April 2003), "President's report 2001–2002", Newsletter of the New Zealand Mathematical Society 87: 4–6.
- Listing of Downey's computer science publications in DBLP.
- Downey, Rod G.; Fellows, Michael R. (1995), "Fixed-parameter tractability and completeness. I. Basic results", SIAM Journal on Computing 24 (4): 873–921, doi:10.1137/S0097539792228228, MR 1342997. Downey, Rod G.; Fellows, Michael R. (1995), "Fixed-parameter tractability and completeness. II. On completeness for W", Theoretical Computer Science 141 (1-2): 109–131, doi:10.1016/0304-3975(94)00097-3, MR 1323150. Downey, Rod; Fellows, Michael (1993), "Fixed-parameter tractability and completeness. III. Some structural aspects of the W hierarchy", Complexity theory, Cambridge: Cambridge Univ. Press, pp. 191–225, MR 1255345. Abrahamson, Karl A.; Downey, Rodney G.; Fellows, Michael R. (1995), "Fixed-parameter tractability and completeness. IV. On completeness for W[P] and PSPACE analogues", Annals of Pure and Applied Logic 73 (3): 235–276, doi:10.1016/0168-0072(94)00034-Z, MR 1336643.
- Awards, New Zealand Mathematical Society, retrieved 2012-02-19.
- List of Current Fellows of the Royal Society of New Zealand, retrieved 2012-02-19.
- ACM Fellow award citation, retrieved 2012-02-19.
- Professor Downey Becomes ACM Fellow, Victoria University of Wellington, 6 December 2007, retrieved 2012-02-19.
- Shoenfield Prize Recipients, Association for Symbolic Logic, retrieved 2012-02-19.
- Hector Medal to Rod Downey, New Zealand Mathematical Society, 16 November 2011, retrieved 2012-02-19.
- Medals awarded to top New Zealand researchers, RSNZ, 17 November 2011, retrieved 2012-02-19.
- List of Fellows of the American Mathematical Society, retrieved 2012-11-10.
- Home page at Victoria University of Wellington