Professor Michael Fellows is recognized as one of the founders of parameterized complexity, a complexity framework that uses structure in hard problems for the design and analysis of algorithms for their solution. Parameterized complexity has strong connections to algorithmic engineering, and is increasingly important in fields as diverse as Artificial Intelligence, Cognitive Science, and Bioinformatics.
The current challenge Professor Fellows has embraced is to combine this world-leading research with new complexity theory to understand the effectiveness of practical heuristics on real-world datasets, and to systematically design and improve heuristics, based on theory and experiments. He was awarded a Toppforsk grant of about NOK 25 million for his project, “Parameterized Complexity for Practical Computing”, and the grant proposal is available here.
Some of the impactful approaches he is developing include turbocharging heuristics with FPT modules. Fellows' program of reverse kernelization involves incorporating where the data comes from. Together with data visualization, this can significantly contribute to "big data" analysis. It is inevitable that there should be a theory of groovy FPT. The theme here is paying attention to the Structure of Argumentation, such as induction or minimum counter-example. The research answers questions as to how much axiomatic power do you need to prove a particular theorem or to support theorems in computational complexity or multivariate analysis.
Michael Fellows has worked with outreach and science communication in various ways, and here are some selected highlights:
Computer Science Unplugged!
Fellows is the 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.
Invited talks and research visits
Fellows is a plenary speaker at 3 – 5 events annually, and may give short course during research visits. A particular highlight was the KVPY Vijyoshi Science Camp in 2012, where he spoke to about 600 extremely talented students.
Another highlight was the talk "Parameterized Algorithms And Complexity: How The Field Began And Where It May Go", which he was invited to do at the Institute of Mathematical Sciences in India.
Passion plays about mathematics
Fellows is also known for his innovative science communication, and is the author of several passion plays about mathematics, with mathematical proofs enacted on-stage. The plays were performed at the Fringe Theatre in British Columbia.
Advice to students
In 2016, the Bulletin of the European Association for Theoretical Computer Science (EATCS) published Fellows' letter Are you Interested in Theoretical Computer Science? (How Not???) I Have Some Advice for You.
- (2022). Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. Artificial Intelligence.
- (2021). Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Springer Series in Computer Science.
- (2020). Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory. IJCAI International Joint Conference on Artificial Intelligence. 1119-1125.
- (2018). Parameterized approximation via fidelity preserving transformations. Journal of computer and system sciences. 30-40.
- (2018). A brief history of Edward K. Blum and the Journal of Computer and System Sciences. Journal of computer and system sciences. 2-10.
- (2017). Surfing with rod. Lecture Notes in Computer Science (LNCS). 9-18.
- (2017). Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number. Discrete Applied Mathematics. 94-100.
- (2016). Tractable parameterizations for the MINIMUM LINEAR ARRANGEMENT problem. ACM Transactions on Computation Theory.
- (2021). Parameterized String Equations abs/2104.14171.
- (2018). Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday.
- (2018). Corrigendum to 'Advice classes of parameterized tractability' [Ann. Pure Appl. Logic 84 (1) (1997) 119-138] (S0168007295000208) (10.1016/S0168-0072(95)00020-8)). Annals of Pure and Applied Logic. 463-465.
Michael Fellows has published over 200 articles in high-quality peer reviewed journals and conference proceedings. He has also written 2 books on Parameterized Complexity (with Rod Downey), edited Special Issues, and co-authored book chapters. An overview of his publications is available here.
Fellows' ability to lead research fields with key new ideas and to establish new interdisciplinary approaches is evident from the following selected honours and rewards:
- 2016: Order of Australia, Companion to the Queen (AC). This is Australia's highest civilian honour, similar to UK knighthood. To appreciate this requires a trip to Wikipedia: Of the approximately 400 over the 50 years of the Australian national honours system, over all walks of life (politicians, sports stars, movie stars…) there have been approximately 60 AC academics, of which there are approximately 30 scientists, and of those, 6 Nobel Laureates. Fellows is the first computer scientist to receive this honour.
- 2014: Honorary Fellow of the Royal Society of New Zealand. He is the second person whose primary research area is algorithms to receive this honor, after Dantzig. Honorary Fellows include Einstein, Bohr, Curie, Darwin, Fleming, Priestley, Richter, Rutherford, altogether 230 since 1870.
- 2014: International Gold Medal of Honor for Computer Science and Computer Science Education, ETH University of Zurich, for "Computer Science Unplugged! sharing the foundations and open questions of computer science with students of all ages". Computer Schience Unplugged! is now translated into 23 languages.