Professor Rod Downey | |
---|---|

Born | September 20, 1957 |

Nationality | New Zealander, Australian |

Occupation | Professor of Mathematics, Victoria University of Wellington |

Known for | Computability theory, incl. parameterised complexity |

Awards | RSNZ Hector Medal and Rutherford Medal |

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 an New Zealand and Australian mathematician and computer scientist,^{ [2] } a 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.

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, and was given a personal chair at Victoria in 1995.^{ [1] }^{ [2] }

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

Downey is the co-author of three books:

*Parameterized Complexity*(with Michael Fellows, Springer, 1999)*Algorithmic Randomness and Complexity*(with D. Hirschfeldt, Springer, 2010)*Fundamentals of Parameterized Complexity*(with Michael Fellows, Springer, 2013)

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] }

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] }, New Zealand Mathematical Society, retrieved 19 February 2012. 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] } 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.^{ [13] } 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."^{ [14] }^{ [15] } In 2012 he became a fellow of the American Mathematical Society.^{ [16] } 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 Goedel Lecture of the Association for Symbolic Logic in the European Summer Meeting at Udine, Italy. In 2018, 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."^{ [17] }

**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.

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

**Michael Oser Rabin** is an Israeli mathematician and computer scientist and a recipient of the Turing Award.

**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.

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 by the number of bits in the input. The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

**Michael Fredric Sipser** is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of Applied Mathematics and Dean of Science at the Massachusetts Institute of Technology.

The **Association for Symbolic Logic** (**ASL**) is an international organization of specialists in mathematical logic and philosophical logic. The ASL was founded in 1936, and its first president was Alonzo Church. The current president of the ASL is Julia F. Knight.

**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.

**Avi Wigderson** is an Israeli mathematician and computer scientist. He is professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural networks.

**Michael George Luby** is a mathematician and computer scientist, research director of the core technologies for transport, communications and storage group at the International Computer Science Institute (ICSI), former VP Technology at Qualcomm, co-founder and former Chief Technology Officer of Digital Fountain. In coding theory he is known for leading the invention of the Tornado codes and the LT codes. In cryptography he is known for his contributions showing that any one-way function can be used as the basis for private cryptography, and for his analysis, in collaboration with Charles Rackoff, of the Feistel cipher construction. His distributed algorithm to find a maximal independent set in a computer network has also been very influential. He has also contributed to average-case complexity.

**Alex James Wilkie** FRS is a British mathematician known for his contributions to model theory and logic. Previously Reader in Mathematical Logic at the University of Oxford, he was appointed to the Fielden Chair of Pure Mathematics at the University of Manchester in 2007.

**Moshe Ya'akov Vardi** is an Israeli mathematician and computer scientist. He is a Professor of Computer Science at Rice University, United States. He is University Professor, the Karen Ostrum George Professor in Computational Engineering, Distinguished Service Professor, and Director of the Ken Kennedy Institute for Information Technology. His interests focus on applications of logic to computer science, including database theory, finite-model theory, knowledge in multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He is an expert in model checking, constraint satisfaction and database theory, common knowledge (logic), and theoretical computer science.

**Ronald Fagin** is an American mathematician and computer scientist, and IBM Fellow at the IBM Almaden Research Center. He is known for his work in database theory, finite model theory, and reasoning about knowledge.

**Michael Ralph **"**Mike**"** 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.

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

**Robert Ian Goldblatt** is a mathematical logician who is Emeritus Professor in the School of Mathematics and Statistics at Victoria University, Wellington, New Zealand. His most popular books are *Logics of Time and Computation* and *Topoi: the Categorial Analysis of Logic*. He has also written a graduate level textbook on hyperreal numbers which is an introduction to nonstandard analysis.

**Toniann Pitassi** is a Canadian and American mathematician and computer scientist specializing in computational complexity theory.

**Stevo Todorčević** is a Yugoslavian mathematician specializing in mathematical logic and set theory. He holds a Canada Research Chair in mathematics at the University of Toronto, and a director of research position at the Centre national de la recherche scientifique in Paris.

**Joseph Robert Shoenfield** was an American mathematical logician.

**Martin Grohe** is a German mathematician and computer scientist known for his research on parameterized complexity, mathematical logic, finite model theory, the logic of graphs, database theory, and descriptive complexity theory. He is a University Professor of Computer Science at RWTH Aachen University, where he holds the Chair in Logic and the Theory of Discrete Systems.

- 1 2 3 4 5 6 7 Curriculum vitae, retrieved 19 February 2012.
- 1 2 Whittle, Geoff (August 2004), "Centrefold: Rod Downey" (PDF),
*Newsletter of the New Zealand Mathematical Society*,**91**. - 1 2 Faculty profile, Victoria University of Wellington, retrieved 19 February 2012.
- ↑ Rodney Graham Downey at the Mathematics Genealogy Project
- ↑ Downey, Rod (April 2003), "President's report 2001–2002" (PDF),
*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, 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 . - ↑
- ↑ Awards
- ↑ List of Current Fellows of the Royal Society of New Zealand, retrieved 19 February 2012.
- ↑ ACM Fellow award citation, retrieved 19 February 2012.
- ↑ Professor Downey Becomes ACM Fellow, Victoria University of Wellington, 6 December 2007, retrieved 19 February 2012.
- ↑ Shoenfield Prize Recipients, Association for Symbolic Logic, retrieved 19 February 2012.
- ↑ Hector Medal to Rod Downey, New Zealand Mathematical Society, 16 November 2011, retrieved 19 February 2012.
- ↑ Medals awarded to top New Zealand researchers, RSNZ, 17 November 2011, retrieved 19 February 2012.
- ↑ List of Fellows of the American Mathematical Society, retrieved 10 November 2012.
- ↑ 2018 Rutherford Medal: Solving ‘Can’t compute’ and is that random sequence really random?

- Home page at Victoria University of Wellington

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.

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.