Algorithms, Love and Adventure

“Speeding up a process by even a small amount can make a big difference to a company,” says Professor Michael Fellows at the Department of Informatics at the University of Bergen (UiB). He is appointed to the University of Bergen through the elite “Toppforsk” programme, funded by the Norwegian government and the Bergen Research Foundation (Bergens Forsknings Stiftelse).

Professor Mike Fellows is recognized as a founder and leader of the relatively new area of computer science known as “parameterized complexity.” This area investigates the intrinsic difficulty of how a problem can be modelled and algorithmically implemented, either in theory or in practice.

“An algorithm is a recipe. An algorithm for baking a pie would take a cup of flour, do such and so. A good algorithm would make a good pie. Mathematically, a good algorithm is one that uses less resources, runs faster, or uses less memory,” the professor explains.

Parameterized complexity identifies features of a problem (parameters) that can be exploited to create faster, better algorithms. For instance, the well-known treewidth parameter measures how much a graph resembles a tree. The data of real-life problems such as natural selection, or chemical and physical processes are often very large and complex, some structure is almost always present.

“For example, a basic problem in bioinformatics is aligning DNA sequences, and one of the problems is finding an optimal alignment.  The size of the input is huge. According to Wikipedia, if you stretched the DNA in one cell all the way out, it would be about 2m long and all the DNA in all your cells put together would be about twice the diameter of the Solar System. Through parameterized algorithms we can capture various aspects of the problem: the number of sequences to be aligned, scheduling of when the analysis is through, the machines one needs, etc. and influence how fast the problem can be solved. We use the parameters to capture the structure of typical instances. It is a theory that works together with practice,” Fellows explains.

Bergen – a powerhouse of algorithmic science

Almost every modern aspect of industry, commerce, government or innovation needs efficient algorithms, whether for scheduling oil production, determining mobile-phone coverage, or coordinating health databases. Algorithms are inherent in all other areas of computer science:  artificial intelligence, computational biology, computer architecture, graphics, robotics, security, networking, etc.

The parameterized complexity branch of computer science is growing, with groups of scientists working together in Australia, China, India, UK, USA, world-wide exploring it further.

Fellows joined UiB in January 2016, moving from Charles Darwin University, Australia. He chose UiB for a reason.

“Europe is leading the way in parameterized, multivariate algorithms, with Bergen as the strongest centre. In this area of research, the UiB Algorithms Group is the strongest research group in the world. The theory has developed mathematically, now is the time to put theory into practice,” Fellows says.

Grass-roots computer science

Fellows is also co-author of  Computer Science Unplugged. The primary goal of the Unplugged project is to promote Computer Science and computing in general to young people as an interesting, engaging, and intellectually stimulating discipline. The book has won several science popularization awards, and been translated into 19 languages including Norwegian, Japanese, Korean, Arabic, Hebrew, Chinese, Spanish, Swedish, and German, with more translations underway.

“It is used all over the world and has become a grass-roots movement. It is very gratifying, because when we wrote the book in the mid-1990s, it was rejected by every major publisher in the world. The rejections were all quite lovely, basically saying that they loved the book, but that it didn’t have any connection to the math curriculum. The math behind computers is a modern kind of math that is not reflected in the curriculum. But times have changed,” says Fellows.

Schools are becoming interested in teaching real computer science, not just web pages or programming. Google is a major player in sponsoring activities based on the Unplugged activities.

In their travels around the world, Fellows and his wife Frances Rosamond, also a scientist, meet, inspire and are inspired by their fellow researchers. They always take some time out to engage children with Computer Science Unplugged activities.

Mathematics on stage

Fellows has also tried his hand at communicating mathematics through theatre.

Mathematics is feared by most people. His four cowboy melodramas, almost vaudeville, address issues in the politics of curiosity and are expected to be provocative. Each play dramatizes deep mathematics that has been part of Fellows’ professional research—he puts a theorem on stage.

He has written, “What is mathematical science all about? I believe it is about the unfolding of our collective cognitive abilities, as part of our natural instinct to develop rich and expressive, as well as useful language. Mathematical science is therefore destined for the theatre, as it is powerfully and inherently metaphorical.”

His expression of the love of math resulted in true love. Fellows met his wife Frances A. Rosamond when she attended his plays at the fringe theatre in Victoria, Canada. She is a computer scientist, who also now works at UiB. The couple share a passion for science and math (especially multivariate algorithms), and communicating to a broader audience, including children.

Explaining science to a ten-year-old

“Teaching children is important in the grand scheme of things. They have a natural curiosity, and it is a two-way street. If you want to talk to someone with a background in biology about computer science, you need a “ten-years old’s” version of the science, and they need to explain biology to me like I am ten years old. It is the universal meeting point for interdisciplinary communications. Explaining your science to a ten-year-old gives you a fresh picture of what you are actually working on,” Fellows says.

The book and his communication of science has won Fellows several awards, one example being the International Gold Medal of Honour for Computer Science and Computer Science Education, given by the ETH University of Zurich.

Fellows is also Honorary Fellow of the Royal Society of New Zealand in 2014, making him one of 230 to receive the honour since 1870. Other fellows of the society include scientists such as Albert Einstein, Niels Bohr, Marie Curie, and Charles Darwin.

“I am the first computer scientist to receive the award,” Fellows says proudly. He is also one of ten inaugural fellows of the European Association for Theoretical Computer Science.