Please read our student and staff community guidance on COVID-19
Skip to main content Skip to navigation

Mike Paterson, FRS

Job Title
Professor
Department
Computer Science
Phone
024 7652 3194
Web Link
Research Interests

Algorithms, discrete maths

  • 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
  • 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
  • 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
  • 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., 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Paterson, Michael S., Srinavasan, Aravind, 1995. Contention resolution with bounded delay. 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, M. S., Dancik, V., 1994. Longest common subsequences. University of Warwick. Department of Computer Science
  • Paterson, Michael S., 1993. Computer science seminars 1992/93. 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
  • 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
  • Fischer, Michael J., Paterson, Michael S., 1992. Fishspear : a priority queue algorithm. 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
  • Paterson, Michael S., Zwick, Uri, 1991. Shrinkage of de Morgan formulae under restriction. 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, 1990. Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions. 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., Pippenger, Nicholas, Zwick, Uri, 1990. Optimal carry save networks. 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, 1989. Binary partitions with applications to hidden-surface removal and solid modelling. 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
  • McColl, William Finlay, Paterson, Michael S., 1988. Planar acyclic computation. 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
  • 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
  • McColl, William Finlay, Paterson, Michael S., 1975. The depth of all Boolean functions. 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