Michael R. Fellows

I have been instrumental in at least four new research areas of theoretical computer science, including Transversals of Partitions of Graphs, Emulation, the Polly Cracker Cryptosystem, and Multivariate Complexity Analysis and Algorithm Design which has its first formation as Parameterized Complexity. I have done early leading work in Graph Minors, including the notion of the strong chromatic number of a graph and transversals of graph partitions. I always believed in providing an application area for my students. Early on in Canada, we worked in Bioinformatics. Of course, this is still an area of vast importance today. Other research areas include Scheduling Problems, the complexity of Logic Problems, and problems in Social Choice .

Sue Whitesides has led several Barbados Workshops in Computational Geometry, to which I have contributed. I have also done research in Cryptography (with Neal Koblitz, founder of elliptic curve cryptology) and coding theory. I have done work in Hypergraph Algorithms and Complexity, Combinatorics, and structure, especially Structural Parameterized Complexity.

The development of the theory behind parameterized complexity, especially the W-hardness hierarchy, includes research involving circuits, and analogues of Cooks Theorem. Some of the development is also found in my survey articles. My work in algorithm design and complexity analysis includes work in the areas of Exact Algorithms and also Approximation, including work in PTAS and EPTAS.

I have also contributed many Design Techniques, including Crown Decompositions, Multicoloured Clique, The Extremal Method, the use of Iterative Compression, and others. In the Foreword to The Computer Journal Special Double Issue on Parameterized Complexity and Algorithms (Vol 51, No 1, 2008), I summarize ten rich subprograms of future work- which includes improving local search, exploring kernelization lower bounds, and improving XP optimality. The field is moving forward dramatically.

My Ph.D. in Computer Science is from the University of California, San Diego in 1985, and M.A., Mathematics, also from UCSD in 1982. I have taught in the United States, Canada, New Zealand and Australia. In 2007, I was an inaugural Fellow of the Institute of Advanced Study (Durham), UK. I am Associate Editor for the Journal of Computer and Systems Sciences, Advising Editor for the Journal of Computer and Systems Sciences Section on Parameterized Complexity, Associate Editor for the ACM Transactions on Algorithms, and in 2008 was Guest Editor for a special double issue of The Computer Journal with 15 surveys on Parameterized Complexity. I am a member of the Steering Committee for the conference series International Symposium on Parameterized and Exact Computation (IPEC), proceedings published by Springer in Lecture Notes in Computer Science.

Picture of Michael and Fran Fellows, Rolf Niedermeier and Helmut Schwarz

President of the Alexander Von Humboldt Foundation Helmut Schwarz, myself, Fran Rolf Niedermeier. I was awarded a von Humboldt Research Award in 2007, and Fran and I have spent most of 2007/2008 in Jena, Germany and Europe.

I am also involved in science communication and popularization. My books “Computer Science Unplugged!” (written with Tim Bell and Ian Witten), and “This is MEGA-Mathematics!” (with Nancy Casey) convey sophisticated concepts such as intractability, sorting networks, and cryptography. They have won several science popularization awards, and been translated into Spanish, Russian, Polish, Swedish, Norwegian, French, Chinese, Korean, Japanese and Urdu. More translations are underway. “Computer ScienceUnplugged!” materials have been part of the famous UK Faraday Christmas Lectures in 2008. My wife Frances Rosamond, also a scientist, and I often put on workshops for school children or teachers.