# Michael Stewart Paterson

Michael Stewart Paterson (1942) é um cientista da computação britânico, que foi diretor do Centre for Discrete Mathematics and its Applications (DIMAP) na Universidade de Warwick até 2007.
Obteve um doutorado na University of Cambridge em 1967, orientado por David Park. Passou três anos no Instituto de Tecnologia de Massachusetts (MIT) e foi para a Universidade de Warwick em 1971, onde é professor emérito.
Paterson é especialista em ciência da computação teórica com mais de 100 publicações, especialmente o projeto e análise de algoritmos e complexidade computacional. A carreira de destaque de Paterson foi reconhecida com o Prêmio EATCS de 2006 da European Association for Theoretical Computer Science e um workshop em comemoração a seu aniversário de 66 anos em 2008, incluindo contribuições de diversos laureados com o Prêmio Turing e o Prêmio Gödel. Um outro workshop foi organizado em 2017 em comemoração a seu aniversário de 75 anos, simultaneamente com um workshop pelo aniversário de 10 anos do DIMAP. Por seu trabalho sobre sistema de processamento distribuído com Michael John Fischer e Nancy Lynch recebeu o Prêmio Dijkstra de 2001, e seu trabalho com Dyer e Goldberg sobre a contagem de homomorfismos de grafos recebeu um best paper award na conferência ICALP (International Colloquium on Automata, Languages and Programming) em 2006. Mike Paterson recebeu um Prêmio Lester R. Ford em 2010. É Membro da Royal Society desde 2001 e foi presidente da European Association for Theoretical Computer Science (EATCS). De acordo com o presidente da Maurice Nivat, Paterson teve um grande papel nofinal da década de 1960 no reconhecimento da computação como uma ciência, "and that theoretical computer science, which is very close to mathematics but distinct in its motivation and inspiration, is indeed a challenging and fruitful field of research."

## Publicações selecionadas

* M. Dyer, L.A. Goldberg and M. Paterson, On counting homomorphisms to directed acyclic graphs, Electronic Colloquium on Computational Complexity, Report TR05-121, Oct 2005.
* L.A. Goldberg, M. Jalsenius, R. Martin and M. Paterson, Improved mixing bounds for the anti-ferromagnetic Potts Model on Z$^2$, 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$^n$-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).