Rod Downey

Last updated

Rod Downey

FRSNZ, FNZMS, FACM
Rod Downey.jpg
Born (1957-09-20) 20 September 1957 (age 66)
Nationality New Zealander, Australian
Occupation(s)Professor of Mathematics, Victoria University of Wellington
Known for Computability theory, incl. parameterised complexity
Awards RSNZ Hector Medal, Rutherford Medal, James Cook Research Fellowship
Academic background
Alma mater Monash (PhD 1982)
Queensland (BSc 1978)
Doctoral advisor John Crossley
Website Here

Rodney Graham Downey (born 20 September 1957) [1] is a New Zealand and Australian mathematician and computer scientist, [2] an emeritus professor in the School of Mathematics and Statistics at Victoria University of Wellington in New Zealand. [3] He is known for his work in mathematical logic and computational complexity theory, and in particular for founding the field of parameterised complexity together with Michael Fellows.

Contents

Biography

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. [1] [3] [4] 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, was given a personal chair at Victoria in 1995, and retired in 2021. [1] [2]

Downey was president of the New Zealand Mathematical Society from 2001 to 2003. [1] [5]

Publications

Downey is the co-author of five books:

He is also the author or co-author of over 200 research papers, [1] [6] including a highly cited sequence of four papers with Michael Fellows and Karl Abrahamson setting the foundation for the study of parameterised complexity. [7]

Awards and honours

In 1990, Downey won the Hamilton Research Award from the Royal Society of New Zealand. [8] 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". [9]

In 1994, he won the New Zealand Association of Scientists Research Award, and became a fellow of the Royal Society of New Zealand in 1996. [1] [10] In 2006, he became the first New Zealand-based mathematician to give an Invited Lecture at the International Congress of Mathematicians.

He has also given invited lectures at the International Congress of Logic, Methodology and Philosophy of Science and the ACM Conference on Computational Complexity. He was elected as an ACM Fellow in 2007 "for contributions to computability and complexity theory", becoming the second ACM Fellow in New Zealand, [11] [12] and in the same year was elected as a fellow of the New Zealand Mathematical Society. [1] Also in 2007 he was awarded a James Cook Research Fellowship for research on the nature of computation. [13]

In 2010 he won the Shoenfield Prize (for articles) of the Association for Symbolic Logic for his work with Denis Hirschfeldt, Andre Nies, and Sebastiaan Terwijn on randomness. [14] 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." [15] [16] In 2012, he became a fellow of the American Mathematical Society. [17] In 2013, he became a Fellow of the Australian Mathematical Society.

In 2014, he was awarded the Nerode Prize from the European Association for Theoretical Computer Science, jointly with Hans Bodlaender, Michael Fellows, Danny Hermelin, Lance Fortnow and Rahul Santhanam for their work on kernelization lower bounds. In October 2016, Downey received a distinguished Humboldt Research Award for his academic contributions.

With Denis Hirschfeldt, Downey won another Shoenfield Prize from the Association for Symbolic Logic, this time the 2016 book prize for Algorithmic Randomness and Complexity. In 2018, Downey delivered the Gödel Lecture of the Association for Symbolic Logic, titled Algorithmic randomness, at the European Summer Meeting at Udine, Italy. The same year, Downey was awarded the Rutherford Medal, the highest honour awarded by the Royal Society of New Zealand, "for his pre-eminent revolutionary research into computability, including development of the theory of parameterised complexity and the algorithmic study of randomness." [18] In 2022, Downey was awarded the New Zealand Association of von Humboldt Fellows Research Award for research over the preceding five years. [19] In 2023, Downey was awarded the S. Barry Cooper Prize from the Association for Computability in Europe. [20] This award is awarded every two to three years "to a researcher who has contributed to a broad understanding and foundational study of computability by outstanding results, by seminal and lasting theory building, by exceptional service to the research communities involved, or by a combination of these." [21]


Related Research Articles

<span class="mw-page-title-main">Gregory Chaitin</span> Argentine-American mathematician

Gregory John Chaitin is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem. He is considered to be one of the founders of what is today known as algorithmic complexity together with Andrei Kolmogorov and Ray Solomonoff. Along with the works of e.g. Solomonoff, Kolmogorov, Martin-Löf, and Leonid Levin, algorithmic information theory became a foundational part of theoretical computer science, information theory, and mathematical logic. It is a common subject in several computer science curricula. Besides computer scientists, Chaitin's work draws attention of many philosophers and mathematicians to fundamental problems in mathematical creativity and digital philosophy.

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

<span class="mw-page-title-main">Juris Hartmanis</span> American computer scientist (1928–2022)

Juris Hartmanis was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

<span class="mw-page-title-main">Jack Dongarra</span> American computer scientist (born 1950)

Jack Joseph Dongarra is an American computer scientist and mathematician. He is the American University Distinguished Professor of Computer Science in the Electrical Engineering and Computer Science Department at the University of Tennessee. He holds the position of a Distinguished Research Staff member in the Computer Science and Mathematics Division at Oak Ridge National Laboratory, Turing Fellowship in the School of Mathematics at the University of Manchester, and is an adjunct professor and teacher in the Computer Science Department at Rice University. He served as a faculty fellow at the Texas A&M University Institute for Advanced Study (2014–2018). Dongarra is the founding director of the Innovative Computing Laboratory at the University of Tennessee. He was the recipient of the Turing Award in 2021.

<span class="mw-page-title-main">Neil Immerman</span> American theoretical computer scientist

Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst. He is one of the key developers of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory.

<span class="mw-page-title-main">Knuth Prize</span> Prize given by ACM and IEEE for outstanding contributions to the foundations of computer science

The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.

<span class="mw-page-title-main">Noga Alon</span> Israeli mathematician

Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.

<span class="mw-page-title-main">Ravindran Kannan</span>

Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.

John Vivian Tucker is a British computer scientist and expert on computability theory, also known as recursion theory. Computability theory is about what can and cannot be computed by people and machines. His work has focused on generalising the classical theory to deal with all forms of discrete/digital and continuous/analogue data; and on using the generalisations as formal methods for system design; based on abstract data types and on the interface between algorithms and physical equipment.

Michael Ralph Fellows AC HFRSNZ MAE is a computer scientist and the Elite Professor of Computer Science in the Department of Informatics at the University of Bergen, Norway as of January 2016.

<span class="mw-page-title-main">Georg Gottlob</span> Austrian computer scientist

Georg Gottlob FRS is an Austrian-Italian computer scientist who works in the areas of database theory, logic, and artificial intelligence and is Professor of Informatics at the University of Calabria. He was Professor at the University of Oxford.

<span class="mw-page-title-main">János Pach</span> Hungarian mathematician

János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.

<span class="mw-page-title-main">Cynthia Dwork</span> American computer scientist

Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.

<span class="mw-page-title-main">Toniann Pitassi</span> Canadian-American computer scientist

Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.

<span class="mw-page-title-main">Oscar H. Ibarra</span>

Oscar H. Ibarra is a Filipino-American theoretical computer scientist, prominent for work in automata theory, formal languages, design and analysis of algorithms and computational complexity theory. He was a Professor of the Department of Computer Science at the University of California-Santa Barbara until his retirement in 2011. Previously, he was on the faculties of UC Berkeley (1967-1969) and the University of Minnesota (1969-1990). He is currently a Distinguished Professor Emeritus at UCSB.

Bakhadyr M. Khoussainov is a computer scientist and mathematician, who was born and educated in the Soviet Union, works in the fields of mathematical logic, computability theory, computable model theory and theoretical computer science. With Anil Nerode, he is the co-founder of the theory of automatic structures, which is an extension of the theory of automatic groups.

Jin-Yi Cai is a Chinese American mathematician and computer scientist. He is a professor of computer science, and also the Steenbock Professor of Mathematical Sciences at the University of Wisconsin–Madison. His research is in theoretical computer science, especially computational complexity theory. In recent years he has concentrated on the classification of computational counting problems, especially counting graph homomorphisms, counting constraint satisfaction problems, and Holant problems as related to holographic algorithms.

The Gödel Lecture is an honor in mathematical logic given by the Association for Symbolic Logic, associated with an annual lecture at the association's general meeting. The award is named after Kurt Gödel and has been given annually since 1990.

References

  1. 1 2 3 4 5 6 7 Curriculum vitae, retrieved 19 February 2012.
  2. 1 2 Whittle, Geoff (August 2004), "Centrefold: Rod Downey" (PDF), Newsletter of the New Zealand Mathematical Society, 91.
  3. 1 2 Faculty profile, Victoria University of Wellington, retrieved 19 February 2012.
  4. ↑ Rodney Graham Downey at the Mathematics Genealogy Project
  5. ↑ Downey, Rod (April 2003), "President's report 2001–2002" (PDF), Newsletter of the New Zealand Mathematical Society, 87: 4–6.
  6. ↑ Listing of Downey's computer science publications in DBLP.
  7. ↑ Downey, Rod G.; Fellows, Michael R. (1995), "Fixed-parameter tractability and completeness. I. Basic results", SIAM Journal on Computing , 24 (4): 873–921, CiteSeerX   10.1.1.408.3389 , doi:10.1137/S0097539792228228, MR   1342997 . Downey, Rod G.; Fellows, Michael R. (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", 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 .
  8. ↑ "Recipients".
  9. ↑ Awards
  10. ↑ List of Current Fellows of the Royal Society of New Zealand, retrieved 19 February 2012.
  11. ↑ ACM Fellow award citation, retrieved 19 February 2012.
  12. ↑ Professor Downey Becomes ACM Fellow, Victoria University of Wellington, 6 December 2007, retrieved 19 February 2012.
  13. ↑ "Search James Cook Fellowship awards 1996–2017". Royal Society Te Apārangi. Retrieved 28 October 2023.
  14. ↑ Shoenfield Prize Recipients, Association for Symbolic Logic, retrieved 19 February 2012.
  15. ↑ Hector Medal to Rod Downey, New Zealand Mathematical Society, 16 November 2011, retrieved 19 February 2012.
  16. ↑ Medals awarded to top New Zealand researchers, RSNZ, 17 November 2011, retrieved 19 February 2012.
  17. ↑ List of Fellows of the American Mathematical Society, retrieved 10 November 2012.
  18. ↑ 2018 Rutherford Medal: Solving ‘Can’t compute’ and is that random sequence really random?
  19. ↑ "NZ Humboldt Association Research Award to Professor Rod Downey | New Zealand Association of von Humboldt Fellows".
  20. ↑ "2023 S. Barry Cooper Prize awarded to Rod G. Downey". 16 March 2023.
  21. ↑ "S. Barry Cooper Prize". 18 July 2019.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.