Michael Fellows

Last updated

Michael Fellows

Born
Michael Ralph Fellows

(1952-06-15) June 15, 1952 (age 70)
San Diego, California, US
NationalityAmerican, Canadian, Australian
Alma mater University of California, San Diego (Ph.D., 1985, Computer Science; M.A.,1982, Mathematics)
Sonoma State University (B.A., 1980, Mathematics)
Scientific career
Fields Computer science
Institutions University of Bergen, Norway
Doctoral advisor Michael Fredman

Michael Ralph Fellows AC HFRSNZ MAE (born June 15, 1952 in Upland, California) is a computer scientist and the Elite Professor of Computer Science in the Department of Informatics at the University of Bergen, Norway as of January 2016. [1]

Contents

Biography

Fellows received his BA in Mathematics from Sonoma State University, and at the University of California, San Diego (UCSD) his M.A. in Mathematics in 1982 and in 1985 his Ph.D. in Computer Science with the dissertation Encoding Graphs in Graphs. [2]

Until January 2016, Fellows was professor at Charles Darwin University, Australia, [3] and Director of the Parameterized Complexity Research Unit (PCRU). [4] He has taught in the United States, Canada, New Zealand and Australia, as well as in the UK and Europe; and has given invited talks around the world.

In 2018, Fellows was awarded membership in Academia Europaea. In 2016, he received Australia's highest civilian honour, the Order of Australia, Companion to the Queen. In 2014 Fellows became one of ten inaugural fellows of the European Association for Theoretical Computer Science. [5] Also in 2014, he was named an Honorary Fellow of the Royal Society of New Zealand [6] (the first computer scientist to receive this honor). In 2007, Fellows was awarded the Alexander von Humboldt Research Award. [7] His German host was Rolf Niedermeier and Mike spent part of 2007 and most of 2008 at the Friedrich-Schiller-Universität in Jena, Germany, working with Niedermeier. Also in 2007, Mike became one of the first Fellows of the Institute of Advanced Study (Durham), UK [8] and a Fellow of Grey College at the University of Durham. He was also awarded an Australian Research Council Professorial Fellowship for five years, beginning 2010. [9]

He is an Area Editor for the Journal of Computer and System Sciences since 2004, and Advising Editor for the special Section on Parameterized Complexity in the same journal. [10] He is Associate Editor for ACM Transactions on Algorithms . [11] In 2008 he was Guest Editor for a special double issue of The Computer Journal containing 15 surveys on parameterized complexity. [12] He is also Guest Editor (with others) for a Special Issue on Parameterized Complexity in the Journal of Combinatorial Optimization to be published in 2010. [13] He is a member of the Steering Committee for the conference series International Workshop on Parameterized and Exact Computation, proceedings published by Springer in Lecture Notes in Computer Science.

Michael Fellows is co-author of Computer Science Unplugged! www.csunplugged.org book and materials, which bring computational thinking activities to youth and adults and have been translated into over 25 languages. He is known for his innovative science communication. He is an organizer of the Creative Mathematical Sciences Communication (CMSC) conference series. An avid interest in politics was inspired by his mother Betty, long a leader in the California League of Women Voters, and a love of literature and movies is shared with his son, Max. Fellows wrote a series of passion plays about mathematics which were presented at the Victoria Fringe Festival and at NCTM at Asilimar in 1999.

In 1999, he married Frances Novak Rosamond, also a scientist, who shares his love of mathematics and adventure.

Honors

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. In 2018, he received the Norwegian Research Council Toppforsk Award for his project, Parameterized Complexity for Practical Computing. The funding scheme supports scientific quality at the forefront of international research; boldness in scientific thinking and innovation.

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.

1) Academy Europaea (MAE) 2018. The Academia Europaea is an independent learned society and European Union's Academy of Humanities and Sciences. On the initiative of Royal Society and other National Academies in Europe, the Academia was founded in 1988 as the functioning Europe-wide Academy that encompasses all fields of scholarly inquiry.

2) Order of Australia, Companion to the Queen (AC) 2016. 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. I am the first computer scientist to receive this honour.

3) Honorary Fellow of the Royal Society of New Zealand (HFRSNZ) 2014. He is the second person whose primary research area is algorithms to receive this honor. Honorary Fellows include Einstein, Bohr, Curie, Darwin, Fleming, Priestley, Richter, Rutherford, altogether 230 since 1870.

4) 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". [14]

5) 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.

6) 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, India and around the world.

Professor Fellow says, “The activities are based on modern research in computer science and mathematics. These materials can be used to make early education more exciting and engaging,” Woven through Computer Science Unplugged is the importance of story: that presenting math and computing topics through story-telling and drama can captivate children and adults alike, and provides a whole new level of engagement. Mike's activities are about thinking outside the box, whether sharing the unknowns of computer science and mathematics with elementary school children or running a mathematics event in a park.”

Mike has been an Australian Professorial Fellow at the University of Newcastle, Australia and at Charles Darwin University, Australia. He is Visiting Professor at Royal Holloway University of London. In 2006, he was an inaugural Fellow of the Institute of Advanced Study, Durham University, and at that time a Best Fellow of Grey College. In 2007, Mike received an Alexander von Humboldt Research Award. He collaborates extensively around the world.

Computer Science Unplugged!

Fellow's books Computer Science Unplugged! [15] written with Tim Bell and Ian Witten, and This is MEGA-Mathematics!, [16] with Nancy Casey convey sophisticated concepts such as intractability, sorting networks, and cryptography. They have won several science popularization awards, and been translated into languages including Japanese, Korean, Arabic, Hebrew, Chinese, Spanish, Swedish, and German, with more translations underway.

Unplugged! was part of the famous British Faraday Christmas Lectures in 2008, which was given by Professor Christopher M. Bishop [17] of UK Microsoft Research.

Passion plays about mathematics

Fellows is also the author of several passion plays about mathematics, with mathematical proofs enacted on-stage, which were performed at the Fringe Theatre in British Columbia.

Publications

He has published five books and over 150 scientific articles [18] [19]

Books and dissertation:

Related Research Articles

Gregory John Chaitin is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem. He is considered to be one of the founders of what is today known as algorithmic complexity together with Andrei Kolmogorov and Ray Solomonoff. Along with the works of e.g. Solomonoff, Kolmogorov, Martin-Löf, and Leonid Levin, algorithmic information theory became a foundational part of theoretical computer science, information theory, and mathematical logic. It is a common subject in several computer science curricula. Besides computer scientists, Chaitin's work draws attention of many philosophers and mathematicians to fundamental problems in mathematical creativity and digital philosophy.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

Michael Randolph Garey is a computer science researcher, and co-author of Computers and Intractability: A Guide to the Theory of NP-completeness. He and Johnson received the 1979 Frederick W. Lanchester Prize from the Operations Research Society of America for the book. Garey earned his PhD in computer science in 1970 from the University of Wisconsin–Madison. He was employed by AT&T Bell Laboratories in the Mathematical Sciences Research Center from 1970 until his retirement in 1999. For his last 11 years with the organization, he served as its director. His technical specialties included discrete algorithms and computational complexity, approximation algorithms, scheduling theory, and graph theory. From 1978 until 1981 he served as Editor-in-Chief of the Journal of the Association for Computing Machinery. In 1995, Garey was inducted as a Fellow of the Association for Computing Machinery.

<span class="mw-page-title-main">Éva Tardos</span> Hungarian mathematician

Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.

<span class="mw-page-title-main">Leslie Valiant</span> British American computer scientist

Leslie Gabriel Valiant is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. Valiant was awarded the Turing Award in 2010, having been described by the A.C.M. as a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science; in particular for his "striking combination of depth and breadth".

<span class="mw-page-title-main">László Babai</span> Hungarian mathematician and computer scientist

László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.

<span class="mw-page-title-main">Kurt Mehlhorn</span> German computer scientist (born 1949)

Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.

Michael Stewart Paterson, is a British computer scientist, who was the director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick until 2007, and chair of the department of computer science in 2005.

Hans Leo Bodlaender is a Dutch computer scientist, a professor of computer science at Utrecht University. Bodlaender is known for his work on graph algorithms and parameterized complexity and in particular for algorithms relating to tree decomposition of graphs.

<span class="mw-page-title-main">Rod Downey</span> Australian mathematician

Rodney Graham Downey is a New Zealand and Australian mathematician and computer scientist, a professor in the School of Mathematics and Statistics at Victoria University of Wellington in New Zealand. He is known for his work in mathematical logic and computational complexity theory, and in particular for founding the field of parameterised complexity together with Michael Fellows.

The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science and the International Symposium on Parameterized and Exact Computation. The prize was offered for the first time in 2013.

<span class="mw-page-title-main">Ian H. Witten</span> Computer scientist in New Zealand

Ian H. Witten is a computer scientist at the University of Waikato, New Zealand. He is a Chartered Engineer with the Institute of Electrical Engineers in London who graduated from the University of Cambridge with a BA and MA in mathematics in 1969 and an M.Sc. in mathematics and computer science from the University of Calgary, where he was a Commonwealth Scholar, in 1970. He received his Ph.D. for Learning to Control in 1976 from the University of Essex, England. Witten discovered temporal-difference learning, inventing the tabular TD(0), the first temporal-difference learning rule for reinforcement learning. Witten is a co-creator of the Sequitur algorithm and conceived and obtained funding for the development of the original WEKA software package for data mining. Witten further made considerable contributions to the field of compression, creating novel algorithms for text and image compression with Alistair Moffat and Timothy C. Bell. He is also one of the major contributors to the digital libraries field, and founder of the Greenstone Digital Library Software.

In the parameterized complexity of algorithms, the klam value of a parameterized algorithm is a number that bounds the parameter values for which the algorithm might reasonably be expected to be practical. An algorithm with a higher klam value can be used for a wider range of parameter values than another algorithm with a lower klam value. The klam value was first defined by Downey and Fellows (1999), and has since been used by other researchers in parameterized complexity both as a way of comparing different algorithms to each other and in order to set goals for future algorithmic improvements.

Giorgio Ausiello is an Italian computer scientist. Born in 1941, in 1966 he graduated in Physics under the supervision of Corrado Böhm. From 1966 to 1980 he served as researcher at the Italian National Research Council (CNR). In 1980 he became Professor of Compilers and Operating Systems at Sapienza University of Rome and since 1990 he has been Professor of Theoretical Computer Science in the Department of Computer, Control and Management Engineering, where he has been until recently the leader of the research group on Algorithm Engineering. At academic level Giorgio Ausiello has been Chairman of the degree in Computer Engineering, Director of the Graduate School, then member of the Academic Senate and finally Chairman of the Research Committee of Sapienza University. In 2012 he has been nominated Professor Emeritus of Sapienza University of Rome.

<span class="mw-page-title-main">Mohammad Hajiaghayi</span> American computer scientist

Mohammad Taghi Hajiaghayi is a computer scientist known for his work in algorithms, game theory, social networks, network design, graph theory, and big data. He has over 200 publications with over 185 collaborators and 10 issued patents.

<span class="mw-page-title-main">Giuseppe F. Italiano</span>

Giuseppe Francesco (Pino) Italiano is an Italian computer scientist. He is a professor of computer science at LUISS University in Rome. He is known for his work in graph algorithms, data structures and algorithm engineering.

Fedor V. Fomin is a professor of Computer Science at the University of Bergen. He is known for his work in algorithms and graph theory. He received his PhD in 1997 at St. Petersburg State University under Nikolai Nikolaevich Petrov.

Martin Grohe is a German mathematician and computer scientist known for his research on parameterized complexity, mathematical logic, finite model theory, the logic of graphs, database theory, and descriptive complexity theory. He is a University Professor of Computer Science at RWTH Aachen University, where he holds the Chair for Logic and Theory of Discrete Systems.

Bakhadyr M. Khoussainov is a computer scientist and mathematician, who was born and educated in the Soviet Union, works in the fields of mathematical logic, computability theory, computable model theory and theoretical computer science. With Anil Nerode, he is the co-founder of the theory of automatic structures, which is an extension of the theory of automatic groups.

Saket Saurabh is an Indian Computer Scientist who is currently the Professor of Theoretical Computer Science at the Institute of Mathematical Sciences, Chennai (IMSc), India and an adjunct faculty at University of Bergen, Norway. He specializes in parameterized complexity, exact algorithms, graph algorithms and game theory. His fundamental contributions to the area of parameterized complexity include procedures for obtaining algorithmic lower bounds, and meta-theorems on preprocessing. Saket Saurabh was awarded the Shanti Swarup Bhatnagar Prize for Science and Technology in Mathematical Sciences in the year 2021.

References

  1. ↑ www.uib.no/en/persons/Michael.Fellows
  2. ↑ Michael Fellows on Mathematical Genealogy Project]. Accessed Dec 7, 2012.
  3. ↑ Michael Fellows Profile University of Newcastle
  4. ↑ PCRU Website Director of the Parameterized Complexity Research Unit under the Division of Research at the University of Newcastle, Australia
  5. ↑ Aceto, Luca (March 5, 2014), "EATCS Fellows class of 2014 named", Process Algebra Diary.
  6. ↑ "Royal Society of New Zealand". Royal Society of New Zealand. Retrieved January 5, 2016.
  7. ↑ 'Fellows Receives Alexander von Humboldt Research Award'
  8. ↑ University of Durham, Institute of Advanced Study Laureate of the Institute of Advanced Study, University of Durham
  9. ↑ University of Newcastle Announcement [ permanent dead link ] Australian Research Council Professorial Fellowship
  10. ↑ Vol51 Issue 1, Journal of Computer and Systems Sciences
  11. ↑ Editorial Board ACM Transactions on Algorithms
  12. ↑ JCSS Editorial Board Archived June 7, 2011, at the Wayback Machine The Computer Journal, Oxford Journals
  13. ↑ IWPEC 2009 International Workshop on Parameterized and Exact Algorithms: IWPEC
  14. ↑ Chita, Efi. "EATCS Fellows". EATCS. Retrieved July 13, 2019.
  15. ↑ Computer Science Unplugged! website
  16. ↑ This is MEGA-Mathematics! Archived July 24, 2008, at the Wayback Machine
  17. ↑ Professor Christopher M. Bishop
  18. ↑ Michael Fellows on DBLP
  19. ↑ Michael Fellows, ACM Authors
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.