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

He earned his Doctor of Philosophy (Ph.D.) from the University of Cambridge in 1967. His advisor was David Park. He worked at the Massachusetts Institute of Technology (MIT) for three years before joining the University of Warwick in 1971. He is still a Professor Emeritus there.

Paterson is an expert in theoretical computer science. He has written over 100 papers, focusing on designing and analyzing algorithms and studying computational complexity. His career was honored with the EATCS Award in 2006. A special workshop celebrated his 66th birthday in 2008. Many notable researchers contributed to the event. Another workshop was held in 2017 to mark his 75th birthday. It took place alongside a DIMAP anniversary celebration.

For his work on distributed computing with Fischer and Lynch, he received the Dijkstra Prize in 2001. His research with Dyer and Goldberg on counting graph homomorphisms won the best paper award at the ICALP conference in 2006. He was honored with the Lester R. Ford Award in 2010. He became a Fellow of the Royal Society in 2001 and served as president of the European Association for Theoretical Computer Science (EATCS).

According to EATCS president Maurice Nivat, Paterson played a key role in the late 1960s in helping people recognize computer science as a science. He noted that theoretical computer science, while similar to mathematics, has its own goals and is a valuable field of study.

Paterson is also an avid mountaineer.

Selected publications

• M. Dyer, L.A. Goldberg, and M. Paterson, "On counting homomorphisms to directed acyclic graphs," Electronic Colloquium on Computational Complexity, Report TR05-121, October 2005.
• L.A. Goldberg, M. Jalsenius, R. Martin, and M. Paterson, "Improved mixing bounds for the anti-ferromagnetic Potts Model on Z," LMS J. Comput. Math. 9 (2006) 1–20.
• L.A. Goldberg, R. Martin, and M. Paterson, "Strong spatial mixing for lattice graphs with fewer colours," SICOMP, 35(2) 486–517 (2005).
• M. Albert and M. Paterson, "Bounds for the growth rate of meander numbers," Proceedings of the 16th Annual International Conference on Formal Power Series and Algebraic Combinatorics, 2004, University of British Columbia (Vancouver, B.C., Canada).
• L.A. Goldberg, M. Jerrum, S. Kannan, and M. Paterson, "A bound on the capacity of backoff and acknowledgement-based protocols," SICOMP, 88 (2004) 313–331.
• M. Adler, P. Berenbrink, T. Friedetzky, L.A. Goldberg, P. Goldberg, and M. Paterson, "A proportionate fair scheduling rule with good worst-case performance," Proc. of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2003), 101–108 (2003).
• L.A. Goldberg, M. Jerrum, and M. Paterson, "The computational complexity of two-state spin systems," Random Structures and Algorithms, 23(2) 133–154 (2003).
• K. Iwama, A. Matsuura, and M. Paterson, "A family of NFAs which need 2 -alpha deterministic states," Theoretical Computer Science 301(1–3), 451–462 (2003).
• L.A. Goldberg, S. Kelk, and M. Paterson, "The complexity of choosing an H-colouring (nearly) uniformly at random," SICOMP, 33(2) 416–432 (2004) copyright SIAM.
• M. Paterson, H. Schroeder, O. Sykora, and I. Vrto, "On permutation communications in all-optical rings," Parallel Processing Letters 12(1), 23–29 (2002).