Coronavirus (Covid-19): Latest updates and information
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, 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
  • 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
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