Michael Fellows is a theory builder. His track record extends to at least four new research lines of Theoretical Computer Science including the theory of Graph Covers, Partition Theory, and a new branch of modern cryptography (with Neal Koblitz) based on multivariate polynomials. He did early leading work on algorithmic aspects of graph minor theory. He is considered a founder of Parameterized Complexity (PC). He has contributed most of the PC pioneering concepts (FPT, kernelization, parameter ecology, and others), provided design techniques (extremal method, crown decompositions, and others), and proved foundational theory-building results. He always believed in providing application areas for his students. Early on in Canada, he applied PC to Bioinformatics. He has led the field to new results on PC and Approximation, Local Search, Scheduling, complexity of Logic Problems, Social Choice, and Computational Geometry, among others.
He has started at least three new areas of theoretical computer science including the theory of Graph Covers, Partition Theory, and Multivariate Complexity Analysis and Algorithm Design which has its first formation as Parameterized Complexity. He has done early leading work in Graph Minors, including the notion of the strong chromatic number of a graph and transversals of graph partitions. He always believed in providing an application area for my students. Early on in Canada, he 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 he has contributed. He has also done research in Cryptography (with Neal Koblitz, founder of elliptic curve cryptology) and coding theory. He has worked 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 Workshop on Parameterized and Exact Computation (IWPEC), 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.