Job Title

Professor

Department

Computer Science

Phone

024 7652 3194

Web Link

Research Interests

Algorithms, discrete maths

- 'Chikin, Nikolay, 'Gurvich, Vladimir, 'Knop, Konstantin, 'Paterson, Michael S., 'Vyalyi, Michael, 2021. 'More about exact slow k-Nim. Integers: Electronic Journal of Combinatorial Number Theory, 21
- Chistikov, Dmitry, Goulko, Olga, Kent, Adrian, Paterson, Michael S., 2020. Globe-hopping. Proceedings of the Royal Society A : mathematical, physical and engineering sciences, 476 (2238)
- Conway, J. H., Paterson, Michael S., Moscow, U. S .S. R., 2020. A headache-causing problem. The American Mathematical Monthly, 127 (4), pp. 291-296
- Aziz, Haris, Bachrach, Yoram, Elkind, Edith, Paterson, Michael S., 2011. False-name manipulations in weighted voting games. Journal of Artificial Intelligence, Vol.40, pp. 57-93
- Paterson, Michael S., Zwick, Uri, 2009. Overhang. American Mathematical Monthly, Vol.116 (No.1), pp. 19-44
- Paterson, Michael S., Peres, Y., Thorup, Mikkel, Winkler, P., Zwick, Uri, 2009. Maximum overhang. American Mathematical Monthly, Vol.116 (No.9), pp. 765-787
- Jurdzinski, Marcin, Paterson, Michael S., Zwick, Uri, 2008. A deterministic subexponential algorithm for solving parity games. SIAM Journal on Computing, Vol.38 (No.4), pp. 1519-1532
- Dyer, Martin, Goldberg, Leslie Ann, Paterson, Michael S., 2007. On counting homomorphisms to directed acyclic graphs. Journal of the ACM, Vol.54 (No.6)
- Goldberg, Leslie Ann, Jerrum, Mark, Paterson, Michael S., 2003. The computational complexity of two-state spin systems. Random Structures & Algorithms, 23 (2), pp. 133-154
- Goldberg, Leslie Ann, Paterson, Michael S., Srinivasan, Aravind, Sweedyk, Elizabeth, 2001. Better approximation guarantees for job-shop scheduling. SIAM Journal on Discrete Mathematics, 14 (1), pp. 67-92
- Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S., Srinivasan, Aravind, 2000. Contention resolution with constant expected delay. Journal of the ACM, 47 (6), pp. 1048-1096
- Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S., Thorup, Mikkel, 1999. On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, 28 (3), pp. 1073-1085
- Paterson, Michael S., Przytycka, Teresa, 1996. On the complexity of string folding. Discrete Applied Mathematics, 71 (1-3), pp. 217-230
- Miltersen, Peter Bro, Paterson, Michael S., Tarui, Jun, 1996. The asymptotic complexity of merging networks. Journal of the ACM, 43 (1), pp. 147-165
- Fischer, Michael J., Paterson, Michael S., 1994. Fishspear : a priority queue algorithm. Journal of the ACM, 41 (1), pp. 3-30
- Zwick, Uri, Paterson, Michael S., 1993. The memory game. Theoretical Computer Science, 110 (1), pp. 169-196

- Adler, Micah, Fich, Faith, Goldberg, Leslie Ann, Paterson, Michael S., 2002. Tight size bounds for packet headers in narrow meshes. In Montanari, U.; Rolim, J. D. P.; Welzl, E. (eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 756-767
- Goldberg, Leslie Ann, Jerrum, Mark, Kannan, Sampath, Paterson, Michael S., 2000. A bound on the capacity of backoff and acknowledgement-based protocols. In Montanari, U.; Rolim, J. D. P; Welzl, E (eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 705-716

- 'Czumaj, Artur, 'Kontogeorgiou, George, 'Paterson, Michael S., 2021. 'Haystack hunting hints and locker room communication. 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), Virtual, Scotland, 12-16 Jul 2021, Published in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 58 : 1-58: 20
- Chistikov, Dmitry, Lisowski, Grzegorz, Paterson, Michael S., Turrini, Paolo, 2019. Convergence of opinion diffusion is PSPACE-complete. AAAI-34th conference on Artificial Intelligence, New York, New York, 7-12 Feb 2020, Published in Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 7103-7110
- Aziz, Haris, Lachish, Oded, Paterson, Michael S., Savani, Rahul, 2009. Power indices in spanning connectivity games. 5th International Conference on Algorithmic Aspects in Information and Management, San Francisco, CA, June 15-17, 2009, Published in Lecture Notes in Computer Science, pp. 55-67
- Paterson, Michael S., Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri, 2008. Maximum overhang. 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, Jan 20-22, 2008, Published in Proceedings of the 19th Annual ACM - SIAM Symposium on Discrete Algorithms, pp. 756-765
- Iwama, Kazuo, Nishimura, Harumichi, Paterson, Michael S., Raymond, Rudy, Yamashita, Shigeru, 2008. Polynomial-time construction of linear network coding. ICALP 2008: 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, 6 - 13 Jul 2008, Published in Lecture Notes in Computer Science, pp. 271-282
- Aziz, Haris, Paterson, Michael S., 2008. Classification of computationally tractable weighted voting games. World Congress on Engineering 2008, Imperial Coll London, London, England, Jul 02-04, 2008, Published in World Congress on Engineering : WCE 2008 : 2-4 July, 2008, Imperial College London, London, U.K, pp. 129-134
- Aziz, Haris, Paterson, Michael S., Leech, Dennis, 2007. Efficient algorithm for designing weighted voting games. 11th IEEE International Multitopic Conference, Lahore, Pakistan, 28-30 Dec 2007, Published in IEEE International Multitopic Conference, 2007. INMIC 2007, pp. 211-216
- Jurdzinski, Marcin, Paterson, Michael S., Zwick, Uri, 2006. A deterministic subexponential algorithm for solving parity games. 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, Jan 2006, Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 117-123
- Paterson, Michael S., Zwick, Uri, 2006. Overhang. 17th ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, JAN, 2006, Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 231-240
- Dyer, Martin, Goldberg, Leslie Ann, Paterson, Michael S., 2006. On counting homomorphisms to directed acyclic graphs. 33rd International Colloquium on Automata, Languages and Programming, Venice, Italy, 10-14 Jul 2006, Published in Lecture Notes in Computer Science, pp. 38-49
- Goldberg, Leslie Ann, Paterson, Michael S., Srinivasan, Aravind, Sweedyk, Elizabeth, 1997. Better approximation guarantees for job-shop scheduling. 8th Annual ACM/SIAM Symposium on Discrete Algorithms, New Orleans, LA, 05-07 Jan 1997, Published in SODA '97 Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pp. 599-608
- Paterson, Michael S., Srinivasan, Aravind, 1995. Contention resolution with bounded delay. 36th Annual Symposium on Foundations of Computer Science (FOCS 95), Milwaukee, WI, 23-25 Oct 1995, Published in 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings, pp. 104-113

- Aziz, Haris, Paterson, Michael S., 2008. Variation in weighted voting games. University of Warwick. Department of Computer Science
- Aziz, Haris, Paterson, Michael S., Leech, Dennis, 2007. Combinatorial and computational aspects of multiple weighted voting games. University of Warwick, Department of Economics
- Aziz, H., Paterson, Michael S., Leech, Dennis, 2007. Efficient algorithm for designing weighted voting games. University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, Jerrum, Mark, Paterson, Michael S., 2001. The computational complexity of two-state spin systems. University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, Jerrum, Mark, Kannan, Sampath, Paterson, Michael S., 2000. A bound on the capacity of backoff and acknowledgement-based protocols. University of Warwick. Department of Computer Science
- Adler, Micah, Fitch, Faith, Goldberg, Leslie Ann, Paterson, Michael S., 2000. Tight size bounds for packet headers in narrow meshes. University of Warwick. Department of Computer Science
- Ravindran, Somasundaram, Gibbons, Alan (Alan M.), Paterson, Michael S., 2000. Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theoretical Computer Science, Elsevier Science BV, pp. 325-342
- Cormode, Graham, Paterson, Michael S., Sahinalp, Suleyman Cenk, Vishkin, Uzi, 1999. Communication complexity of document exchange. University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S., Srinavasan, Aravind, 1998. Contention resolution with constant expected delay. University of Warwick. Department of Computer Science
- Khanna, Sanjeev, Muthukrishnan, S., Paterson, Michael S., 1998. On approximating rectangle tiling and packing. University of Warwick. Department of Computer Science
- Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S., Thorup, Mikkel, 1997. On the approximability of numerical taxonomy (fitting distances by tree metrics). University of Warwick. Department of Computer Science
- Goldberg, Leslie Ann, Paterson, Michael S., Srinavasan, Aravind, Sweedyk, Elizabeth, 1996. Better approximation guarantees for job-shop scheduling. University of Warwick. Department of Computer Science
- Ravindran, Somasundaram, Gibbons, Alan (Alan M.), Paterson, Michael S., 1995. Dense edge-disjoint embedding of complete binary trees in interconnection networks. University of Warwick. Department of Computer Science
- Paterson, Michael S., Przytycka, Teresa, 1995. On the complexity of string folding. University of Warwick. Department of Computer Science
- Miltersen, Peter Bro, Paterson, Michael S., Tarui, Jun, 1995. The asymptotic complexity of merging networks. University of Warwick. Department of Computer Science
- Paterson, Michael S., Srinavasan, Aravind, 1995. Contention resolution with bounded delay. University of Warwick. Department of Computer Science
- Paterson, M. S., Dancik, V., 1994. Longest common subsequences. University of Warwick. Department of Computer Science
- Koizumi, Hirotaka, Maruoka, Akira, Paterson, Michael S., 1993. Consistency of natural relations on sets. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1993. Computer science seminars 1992/93. University of Warwick. Department of Computer Science
- Fischer, Michael J., Paterson, Michael S., 1992. Fishspear : a priority queue algorithm. University of Warwick. Department of Computer Science
- Gibbons, Alan (Alan M.), Paterson, Michael S., 1992. Dense edge-disjoint embedding of binary trees in the mesh. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1992. Shallow multiplication circuits and wise financial investments. University of Warwick. Department of Computer Science
- Zwick, Uri, Paterson, Michael S., 1991. The memory game. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1991. Shrinkage of de Morgan formulae under restriction. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1990. Shallow multiplication circuits. University of Warwick. Department of Computer Science
- Paterson, Michael S., Yao, F. Frances, 1990. Optimal binary space partitions for orthogonal objects. University of Warwick. Department of Computer Science
- Paterson, Michael S., Zwick, Uri, 1990. Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions. University of Warwick. Department of Computer Science
- Paterson, Michael S., Pippenger, Nicholas, Zwick, Uri, 1990. Optimal carry save networks. University of Warwick. Department of Computer Science
- Paterson, Michael S., Yao, F. Frances, 1989. Binary partitions with applications to hidden-surface removal and solid modelling. University of Warwick. Department of Computer Science
- McColl, William Finlay, Paterson, Michael S., 1988. Planar acyclic computation. University of Warwick. Department of Computer Science
- Yao, F. Frances, Dobkin, David P., Edelsbrunner, Herbert, Paterson, Michael S., 1988. Partitioning space for range queries. University of Warwick. Department of Computer Science
- Paterson, Michael S., Razborov, Alexander, 1988. The set of minimal braids is co-NP-complete. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1987. Improved sorting networks with O(log n) depth. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1986. Universal chains and wiring layouts. University of Warwick. Department of Computer Science
- Daykin, D. E., Daykin, J. W., Paterson, Michael S., 1983. On log concavity for order-preserving and order-non-reversing maps of partial orders. University of Warwick. Department of Computer Science
- Munro, J. Ian, Paterson, Michael S., 1978. Selection and sorting with limited storage. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1976. New bounds for formula size. University of Warwick. Department of Computer Science
- McColl, William Finlay, Paterson, Michael S., 1975. The depth of all Boolean functions. University of Warwick. Department of Computer Science
- Valiant, Leslie, Paterson, Michael S., 1975. Circuit size is nonlinear in depth. University of Warwick. Department of Computer Science
- SchÃ¶nhage, Arnold, Paterson, Michael S., Pippenger, Nicholas, 1975. Finding the median. University of Warwick. Department of Computer Science
- Paterson, Michael S., 1974. Complexity of monotone networks for Boolean matrix product. University of Warwick. Department of Computer Science

Title | Funder | Award start | Award end |
---|---|---|---|

The Centre for Discrete Mathematics and its Applications | EPSRC | 26 Mar 2007 | 25 Mar 2013 |

2006 RCUK Academic Fellowship Competition - Complexity Science | RCUK | 01 Oct 2006 | 30 Sep 2011 |

Algorithms for Computing Equilibria in Games - (Fellow - R Savani) | EPSRC | 01 Oct 2006 | 30 Sep 2009 |

Algorithmics of network-sharing games | EPSRC | 01 Jan 2005 | 30 Jun 2007 |

Discontinuous behaviour in the complexity of randomized algorithms | EPSRC | 01 Jan 2004 | 31 Dec 2006 |

ALCOM-FT | EU DGXII | 01 Jun 2000 | 01 Dec 2003 |