It's been applied to efforts as varied as studying aboriginal children in Australia, reconstructing the "tree of life", understanding the evolution of European languages, and even designing better ways to distribute donated food to charities.
That came from a field of algorithm design he founded with computer scientist Professor Michael Fellows, called parameterised complexity.
It generally showed that many apparently intractable computations could become feasible once fixed values were given to certain parameters, such as the amount of input data to be used or the size of object to be computed.
This subject has now developed into an important new branch of theoretical computer science, which now had its own international conferences, books and special issues of journals.
Another of his specialist fields is "algorithmic randomness" - something which could help pick one piece of DNA apart from another, or tell whether one composer plagiarised another.
The medal, awarded by Royal Society Te Apārangi, recognised his outstanding contribution to science, along with his record as a research leader and mentor.
Downey said he was "honoured and somewhat startled" to receive it.
"The first recipient of this award was the great Kiwi mathematician Sir Vaughan Jones after he won the Fields Medal," he said.
"Thus, it is especially rewarding to receive this award as a mathematician and theoretical computer scientist."
Other recipients
Others recognised at the society's Research Honours Dinner this year included Professor Linda Tuhiwai Smith, a renowned academic who received the inaugural Te Puāwaitanga Award for her contributions to Te Ao Māori and indigenous knowledge.
Another new award, Te Tohu Rapuora, was presented by the Health Research Council of New Zealand to the University of Waikato's Te Kotahi Research Institute.
The council also presented its Lily Medal to clinician and University of Auckland researcher Professor Cynthia Farquhar, whose recent trial into intrauterine insemination showed for the first time what benefits the fertility treatment could bring.
Its Bevan Medal went to Dr Colin McArthur, director of research at Auckland District Health Board's Department of Critical Care Medicines, in recognition of his role of several trials that have changed guidelines and practices in intensive care units worldwide.
The society's Thomson Medal went to Otago University ecologist Professor Emerita Carolyn Burns, for her outstanding leadership and service to environmental science and conservation.
Another Otago University conservationist, Dr Helen Taylor, received the Callaghan Medal for her science communication around conservation genetics and threatened species.
The University of Auckland's Distinguished Professor Marston Conder, a world authority on the mathematics of symmetry, was awarded the Jones Medal for his life's work and leadership.
Victoria University mathematical physicist Professor Matt Visser received the Hector Medal for his research into both classical and quantum gravity, including work on black holes, cosmology and "analogue spacetimes".
Dr Bruce Hayward was awarded the Hutton Medal for his outstanding contributions to the knowledge of New Zealand's marine ecology and geology, while Professor Brett Delahunt, of Otago University, was awarded the Hercus Medal for his research on prostate and kidney cancer.
Otago University historian Professor Barbara Brookes, an authority in the history of women, medicine and New Zealand, received the Humanities Aronui Medal for her contribution to humanities scholarship.
Professor Lisa Matisoo-Smith, also of Otago University, was presented the Mason Durie Medal for work that has reshaped our understanding of the last great human migration into the Pacific.
Pre-eminent Treaty of Waitangi scholar Dame Dr Claudia Orange received the Pou Aronui Award for her long service to the humanities.
Associate Professor Suzanne Pitama, of Otago University, was awarded the Metge Medal for her influence on indigenous health education.
Distinguished Professor Geoff Chase was awarded the MacDiarmid Medal for physiological modelling of human metabolism used for "in-silico" testing.
These computer models have been used to treat intensive care patients in New Zealand and overseas, and are being extended to treat type-2 diabetes in other patient groups.
His models are estimated to have saved 350 lives and $6 million to $12m at Christchurch Hospital alone over 12 years, and are bringing us much closer to the ideal of personalised medicine in intensive care.
A research team from AgResearch led by Dr David Hume received the Pickering Medal for work to discover, patent and commercialise a new endophyte for ryegrass.
The endophyte provides ryegrass with high levels of protection against insect pests while maintaining the health and productivity of grazing animals, resulting in large gains in farming productivity.
Early career researchers recognised included Dr Arini Loader, of Victoria University; Dr Mohi Rua, of Waikato University; Associate Professor Maren Wellenreuther of Plant & Food Research; Lettie Roach, a PhD student at Victoria University and Niwa; Dr Jurij Volcic, previously based at University of Auckland but now at Texas A&M University, Dr Carwyn Jones, of Victoria University of Wellington; and Associate Professor Holly Thorpe, of the University of Waikato.
