• E-mailmichael.fellows@uib.no
  • Phone+47 55 58 42 61
  • Visitor Address
    Thormøhlens Gate 55
    5008 Bergen
  • Postal Address
    Postboks 7803
    5020 Bergen

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

Academic article
  • Show author(s) (2022). Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. Artificial Intelligence. 15 pages.
  • Show author(s) (2021). Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Springer Series in Computer Science.
  • Show author(s) (2020). Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory. IJCAI International Joint Conference on Artificial Intelligence. 1119-1125.
  • Show author(s) (2018). Parameterized approximation via fidelity preserving transformations. Journal of computer and system sciences. 30-40.
  • Show author(s) (2018). A brief history of Edward K. Blum and the Journal of Computer and System Sciences. Journal of computer and system sciences. 2-10.
  • Show author(s) (2017). Surfing with rod. Lecture Notes in Computer Science (LNCS). 9-18.
  • Show author(s) (2017). Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number. Discrete Applied Mathematics. 94-100.
  • Show author(s) (2016). Tractable parameterizations for the MINIMUM LINEAR ARRANGEMENT problem. ACM Transactions on Computation Theory.
Academic lecture
  • Show author(s) (2021). Parameterized String Equations abs/2104.14171.
Academic monograph
  • Show author(s) (2018). Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday.
  • Show author(s) (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.

More information in national current research information system (CRIStin)

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.

If you want to be kept up-to-date with the parameterized complexity community and developments in the field, refer to the Parameterized Complexity Newsletter and the Parameterized Complexity wiki

See also professor Fellows' facebook page @MikeFellowsFPT

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.