Rodney Graham Downey (born 20 September 1957) is a New Zealand and Australian mathematician and computer scientist,. an emeritus professor in the School of Mathematics and Statistics at

Victoria University of Wellington Victoria University of Wellington (), also known by its shorter names "VUW" or "Vic", is a public university, public research university in Wellington, New Zealand. It was established in 1897 by Act of New Zealand Parliament, Parliament, and w ...

in New Zealand.Faculty profile
Victoria University of Wellington, retrieved 19 February 2012. He is known for his work in

mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

and

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, and in particular for founding the field of parameterised complexity together with

Michael Fellows Michael Ralph Fellows AC HFRSNZ MAE (born June 15, 1952 in Upland, California) 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. Biogra ...

Biography

Downey earned a bachelor's degree at the

University of Queensland The University of Queensland is a Public university, public research university located primarily in Brisbane, the capital city of the Australian state of Queensland. Founded in 1909 by the Queensland parliament, UQ is one of the six sandstone ...

in 1978, and then went on to graduate school at

Monash University Monash University () is a public university, public research university based in Melbourne, Victoria (state), Victoria, Australia. Named after World War I general Sir John Monash, it was founded in 1958 and is the second oldest university in the ...

, earning a doctorate in 1982 under the supervision of John Crossley.Curriculum vitae
retrieved 19 February 2012. After holding teaching and visiting positions at the

Chisholm Institute of Technology Monash University, Caulfield campus is a campus of Monash University located in Caulfield East, Victoria, Caulfield East, which is a suburb of Melbourne, Australia, in the state of Victoria (Australia), Victoria. The campus comprises 13,400 stu ...

Western Illinois University Western Illinois University (WIU) is a public university in Macomb, Illinois, United States. It was founded in 1899 as Western Illinois State Normal School. As the normal school grew, it became Western Illinois State Teachers College. Once West ...

, the

National University of Singapore The National University of Singapore (NUS) is a national university, national Public university, public research university in Singapore. It was officially established in 1980 by the merging of the University of Singapore and Nanyang University ...

, and the

University of Illinois at Urbana-Champaign The University of Illinois Urbana-Champaign (UIUC, U of I, Illinois, or University of Illinois) is a public land-grant research university in the Champaign–Urbana metropolitan area, Illinois, United States. Established in 1867, it is the f ...

, 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 2023. Downey was president of the New Zealand Mathematical Society from 2001 to 2003.

Publications

Downey is the co-author of six books: *''Parameterized Complexity'' (with

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

, Springer, 2013) *''Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees'' (with Keng Meng Ng and David Reed Solomon, Memoirs American Mathematical Society, Vol. 2184, 2020) *''A Hierarchy of Turing Degrees'' (with Noam Greenberg, Annals of Mathematics Studies No. 206, Princeton University Press, 2020) *''Computability and Complexity: Foundations and Tools for Pursuing Scientific Applications, (Springer-Verlag Texts in Computer Science, 2024) He is also the author or co-author of around 300 research papers, including a highly cited sequence of four papers with Michael Fellows and Karl Abrahamson setting the foundation for the study of parameterised complexity.

Awards and honours

In 1990, Downey won the Hamilton Research Award from the Royal Society of New Zealand. 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". 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. In 2006, he became the first New Zealand-based mathematician to give an Invited Lecture at the

International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the IMU Abacus Medal (known before ...

. 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 ACM Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals ...

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. Also in 2007 he was awarded a James Cook Research Fellowship for research on the nature of computation. In 2010 he won the Shoenfield Prize (for articles) of the

Association for Symbolic Logic 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 Curt John Ducasse. The current president of the ASL ...

for his work with Denis Hirschfeldt, Andre Nies, and Sebastiaan Terwijn on

randomness In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. ...

. 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 The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

. In 2013, he became a Fellow of the

Australian Mathematical Society The Australian Mathematical Society (AustMS) was founded in 1956 and is the national society of the mathematics profession in Australia. One of the society's listed purposes is to promote the cause of mathematics in the community by representing ...

. In 2014, he was awarded the

Nerode Prize The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of parameterized complexity, multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science an ...

from the

European Association for Theoretical Computer Science The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as ...

, jointly with Hans Bodlaender, Michael Fellows, Danny Hermelin,

Lance Fortnow Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in Computational complexity theory, computational complexity and interactive proof systems. Since 2019, he has been at the Illinois Institute of Technology ...

and Rahul Santhanam for their work on

kernelization In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solvi ...

lower bounds. In October 2016, Downey received a distinguished

Humboldt Research Award The Humboldt Research Award (), also known informally as the Humboldt Prize, is an award given by the Alexander von Humboldt Foundation of Germany to internationally renowned scientists and scholars who work outside of Germany in recognition of t ...

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

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." In 2022, Downey was awarded the New Zealand Association of von Humboldt Fellows Research Award for research over the preceding five years. In 2023, Downey was awarded the S. Barry Cooper Prize from the Association for Computability in Europe. 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." In 2024, Downey was awarded the New Zealand Mathematics Society Kalman Prize "for a single publication of original research, which may be an article, monograph or book, having appeared within the last 5 calendar years: 2019-2024". This publication was the monograph "A Hierarchy of Turing Degrees" published in the Annals of Mathematics Studies, jointly written with Noam Greenberg.

References

External links

Home page
at Victoria University of Wellington {{DEFAULTSORT:Downey, Rodney G. Living people Australian computer scientists Australian mathematicians New Zealand computer scientists University of Queensland alumni Monash University alumni Academic staff of Victoria University of Wellington Theoretical computer scientists Mathematical logicians Fellows of the American Mathematical Society 2007 fellows of the Association for Computing Machinery Fellows of the Royal Society of New Zealand 1957 births 20th-century New Zealand mathematicians 21st-century New Zealand mathematicians Recipients of the Rutherford Medal James Cook Research Fellows