“Half of science is asking the right questions.” Roger Bacon
Michael R. Fellows
School of Engineering and IT
Honourary Appointment: Royal Holloway,
Humboldt Research Fellow
Dagstuhl Seminar 12241 Data Reduction and Problem Kernels June 10 – 15, 2012 was the occasion to honour Michael R. Fellows on the Occasion of His 60th Birthday. He was presented with a Springer festschrift: The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated Michael R. Fellows on the Occasion of His 60th Birthday. Editors: Hans L. Bodlaender and Rod Downey and Fedor V. Fomin and Daniel Marx. Springer LNCS 7370, DOI 10.1007/978-3- 642-30891-8_8), 2012.
Mike Fellows has won three major awards in 2014.
1) EATCS Fellow 2014. Mike has been conferred one of the inaugural first 10 EATCS Fellows for "his role in founding the field of parameterized complexity theory, which has become a major subfield of research in theoretical computer science, and for being a leader in computer science education" (http://www.eatcs.org/index.php/eatcs-fellows). The award will be presented at ICALP.
2) EATCS-NERODE Prize 2014. This award at ALGO/ESA and is for a series of papers on how to establish lower bounds on kernelization. The two papers and prize winners are: On problems without polynomial kernels, Hans Bodlaender, Rodney Downey, Michael Fellows, Danny Hermelin. Journal of Computer and System Sciences 2009. Infeasibility of instance compression and succinct PCPs for NP, Lance Fortnow, Rahul Santhanam, same journal 2011.
3) ABZ International Medal of Honor for Fundamental Contributions to Computer Science Education. This award through ETH-Zurich is for Mike’s outreach to kids and the community. Fellows wrote “Computer Science Unplugged!” (www.csunplugged.org with New Zealand colleagues Tim Bell (University of Canterbury, NZ) and Ian Witten (Otago University, NZ). activities are the basis of workshops sponsored by Google across the world. They are used in codeweek.au and in curriculum in UK. The book has been translated into 19 languages. It is a global grass-roots movement. Mike and Frances Rosamond give workshops to Aboriginal schools in Australia, and to classrooms in Norway, India and around the world.
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.
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.