Journal Article

Iwama, Kazuo and Paterson, Mike (2022) Bounded Hanoi. The American Mathematical Monthly, 129 (4). pp. 303-319. doi:10.1080/00029890.2022.2026166 ISSN 1930-0972.

Czumaj, Artur, Kontogeorgiou, George and Paterson, Mike (2022) Haystack hunting hints and locker room communication. Random Structures & Algorithms . doi:10.1002/rsa.21114 ISSN 1042-9832. (In Press)

Chikin, Nikolay, Gurvich, Vladimir, Knop, Konstantin, Paterson, Michael S. and Vyalyi, Michael (2021) More about exact slow k-Nim. Integers: Electronic Journal of Combinatorial Number Theory, 21 . G4. ISSN 1553-1732.

Chistikov, Dmitry, Goulko, Olga, Kent, Adrian and Paterson, Michael S. (2020) Globe-hopping. Proceedings of the Royal Society A : mathematical, physical and engineering sciences, 476 (2238). doi:10.1098/rspa.2020.0038 ISSN 1364-5021.

Conway, J. H., Paterson, Michael S. and Moscow, U. S .S. R. (2020) A headache-causing problem. The American Mathematical Monthly, 127 (4). pp. 291-296. doi:10.1080/00029890.2020.1712168 ISSN 0002-9890.

Aziz, Haris, Bachrach, Yoram, Elkind, Edith and Paterson, Michael S. (2011) False-name manipulations in weighted voting games. Journal of Artificial Intelligence, Vol.40 . pp. 57-93. doi:10.1613/jair.3166 ISSN 1076-9757.

Paterson, Michael S., Peres, Y., Thorup, Mikkel, Winkler, P. and Zwick, Uri (2009) Maximum overhang. American Mathematical Monthly, Vol.116 (No.9). pp. 765-787. doi:10.4169/000298909x474855 ISSN 0002-9890.

Paterson, Michael S. and Zwick, Uri (2009) Overhang. American Mathematical Monthly, Vol.116 (No.1). pp. 19-44. doi:10.4169/000298909x474855 ISSN 0002-9890.

Jurdzinski, Marcin, Paterson, Michael S. and Zwick, Uri (2008) A deterministic subexponential algorithm for solving parity games. SIAM Journal on Computing, Vol.38 (No.4). pp. 1519-1532. doi:10.1137/070686652 ISSN 0097-5397.

Dyer, Martin, Goldberg, Leslie Ann and Paterson, Michael S. (2007) On counting homomorphisms to directed acyclic graphs. Journal of the ACM, Vol.54 (No.6). Article: 27. doi:10.1145/1314690.1314691 ISSN 0004-5411.

Goldberg, Leslie Ann, Jerrum, Mark and Paterson, Michael S. (2003) The computational complexity of two-state spin systems. Random Structures & Algorithms, Volume 23 (Number 2). pp. 133-154. doi:10.1002/rsa.10090 ISSN 1042-9832.

Goldberg, Leslie Ann, Paterson, Michael S., Srinivasan, Aravind and Sweedyk, Elizabeth (2001) Better approximation guarantees for job-shop scheduling. SIAM Journal on Discrete Mathematics, Volume 14 (Number 1). pp. 67-92. doi:10.1137/S0895480199326104 ISSN 0895-4801.

Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S. and Srinivasan, Aravind (2000) Contention resolution with constant expected delay. Journal of the ACM, Volume 47 (Number 6). pp. 1048-1096. ISSN 0004-5411.

Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S. and Thorup, Mikkel (1999) On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, Volume 28 (Number 3). pp. 1073-1085. ISSN 0097-5397.

Paterson, Michael S. and Przytycka, Teresa (1996) On the complexity of string folding. Discrete Applied Mathematics, Volume 71 (Number 1-3). pp. 217-230. ISSN 0166-218X.

Miltersen, Peter Bro, Paterson, Michael S. and Tarui, Jun (1996) The asymptotic complexity of merging networks. Journal of the ACM, Volume 43 (Number 1). pp. 147-165. ISSN 0004-5411.

Fischer, Michael J. and Paterson, Michael S. (1994) Fishspear : a priority queue algorithm. Journal of the ACM, Volume 41 (Number 1). pp. 3-30. doi:10.1145/174644.174645 ISSN 0004-5411.

Zwick, Uri and Paterson, Michael S. (1993) The memory game. Theoretical Computer Science, Volume 110 (Number 1). pp. 169-196. doi:10.1016/0304-3975(93)90355-W ISSN 0304-3975.

Book Item

Adler, Micah, Fich, Faith, Goldberg, Leslie Ann and Paterson, Michael S. (2002) Tight size bounds for packet headers in narrow meshes. In: Montanari, U. and Rolim, J. D. P. and Welzl, E., (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, Volume 1853 . Springer Berlin Heidelberg, pp. 756-767. ISBN 9783540677154

Goldberg, Leslie Ann, Jerrum, Mark, Kannan, Sampath and Paterson, Michael S. (2000) A bound on the capacity of backoff and acknowledgement-based protocols. In: Montanari, U. and Rolim, J. D. P and Welzl, E, (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, Volume 1853 . Springer Berlin Heidelberg, pp. 705-716. ISBN 9783540677154

Conference Item

Czumaj, Artur, Kontogeorgiou, George and Paterson, Michael S. (2021) Haystack hunting hints and locker room communication. In: 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), 198 58 : 1-58: 20. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.58 ISSN 1868-8969.

Chistikov, Dmitry, Lisowski, Grzegorz, Paterson, Michael S. and Turrini, Paolo (2019) Convergence of opinion diffusion is PSPACE-complete. In: 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. and Savani, Rahul (2009) Power indices in spanning connectivity games. In: 5th International Conference on Algorithmic Aspects in Information and Management, San Francisco, CA, June 15-17, 2009. Published in: Lecture Notes in Computer Science, Vol.5564 pp. 55-67. ISBN 978-3-642-02157-2. doi:10.1007/978-3-642-02158-9_7 ISSN 0302-9743.

Aziz, Haris and Paterson, Michael S. (2008) Classification of computationally tractable weighted voting games. In: 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., Vol.1-2 pp. 129-134. ISBN 978-988-98671-9-5. ISSN 2078-0966.

Paterson, Michael S., Peres, Yuval, Thorup, Mikkel, Winkler, Peter and Zwick, Uri (2008) Maximum overhang. In: 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. ISBN 978-0-898716-47-4.

Iwama, Kazuo, Nishimura, Harumichi, Paterson, Michael S., Raymond, Rudy and Yamashita, Shigeru (2008) Polynomial-time construction of linear network coding. In: ICALP 2008: 35th International Colloquium on Automata, Languages and Programming , Reykjavik, Iceland, 6 - 13 Jul 2008 . Published in: Lecture Notes in Computer Science, Vol.5125 pp. 271-282. doi:10.1007/978-3-540-70575-8_23 ISSN 0302-9743.

Aziz, Haris, Paterson, Michael S. and Leech, Dennis (2007) Efficient algorithm for designing weighted voting games. In: 11th IEEE International Multitopic Conference, Lahore, Pakistan, 28-30 Dec 2007. Published in: IEEE International Multitopic Conference, 2007. INMIC 2007. pp. 211-216. ISBN 9781424415526. doi:10.1109/INMIC.2007.4557718

Dyer, Martin, Goldberg, Leslie Ann and Paterson, Michael S. (2006) On counting homomorphisms to directed acyclic graphs. In: 33rd International Colloquium on Automata, Languages and Programming, Venice, Italy, 10-14 Jul 2006. Published in: Lecture Notes in Computer Science, Volume 4051 pp. 38-49. ISBN 3-540-35904-4. doi:10.1007/11786986_5 ISSN 0302-9743.

Paterson, Michael S. and Zwick, Uri (2006) Overhang. In: 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. ISBN 978-0-89871-605-4. doi:10.1145/1109557.1109584 ISSN 9780898716054.

Jurdzinski, Marcin, Paterson, Michael S. and Zwick, Uri (2006) A deterministic subexponential algorithm for solving parity games. In: 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. ISBN 978-0-89871-605-4. ISSN 9780898716054.

Goldberg, Leslie Ann, Paterson, Michael S., Srinivasan, Aravind and Sweedyk, Elizabeth (1997) Better approximation guarantees for job-shop scheduling. In: 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. ISBN 0898713900.

Paterson, Michael S. and Srinivasan, Aravind (1995) Contention resolution with bounded delay. In: 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. ISBN 0818671831. ISSN 0272-5428.

Working or Discussion Paper

Aziz, Haris, Paterson, Michael S. and Leech, Dennis (2007) Combinatorial and computational aspects of multiple weighted voting games. Working Paper. Coventry: University of Warwick, Department of Economics. Warwick economic research papers (No.823).

Journal Item

Ravindran, Somasundaram, Gibbons, Alan (Alan M.) and Paterson, Michael S. (2000) Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theoretical Computer Science, Volume 249 (Number 2). pp. 325-342.

Report

Aziz, Haris and Paterson, Michael S. (2008) Variation in weighted voting games. Coventry: University of Warwick. Department of Computer Science. (Unpublished)

Aziz, H., Paterson, Michael S. and Leech, Dennis (2007) Efficient algorithm for designing weighted voting games. University of Warwick. Department of Computer Science. (Department of Computer Science Research Report).

Goldberg, Leslie Ann, Jerrum, Mark and Paterson, Michael S. (2001) The computational complexity of two-state spin systems. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Goldberg, Leslie Ann, Jerrum, Mark, Kannan, Sampath and Paterson, Michael S. (2000) A bound on the capacity of backoff and acknowledgement-based protocols. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Adler, Micah, Fitch, Faith, Goldberg, Leslie Ann and Paterson, Michael S. (2000) Tight size bounds for packet headers in narrow meshes. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Cormode, Graham, Paterson, Michael S., Sahinalp, Suleyman Cenk and Vishkin, Uzi (1999) Communication complexity of document exchange. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S. and Srinavasan, Aravind (1998) Contention resolution with constant expected delay. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Khanna, Sanjeev, Muthukrishnan, S. and Paterson, Michael S. (1998) On approximating rectangle tiling and packing. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Agarwala, Richa, Bafna, Vineet, Farach, Martin, Paterson, Michael S. and Thorup, Mikkel (1997) On the approximability of numerical taxonomy (fitting distances by tree metrics). University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Goldberg, Leslie Ann, Paterson, Michael S., Srinavasan, Aravind and Sweedyk, Elizabeth (1996) Better approximation guarantees for job-shop scheduling. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. and Srinavasan, Aravind (1995) Contention resolution with bounded delay. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Miltersen, Peter Bro, Paterson, Michael S. and Tarui, Jun (1995) The asymptotic complexity of merging networks. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Ravindran, Somasundaram, Gibbons, Alan (Alan M.) and Paterson, Michael S. (1995) Dense edge-disjoint embedding of complete binary trees in interconnection networks. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. and Przytycka, Teresa (1995) On the complexity of string folding. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, M. S. and Dancik, V. (1994) Longest common subsequences. Coventry: University of Warwick. Department of Computer Science. (Unpublished)

Paterson, Michael S. (1993) Computer science seminars 1992/93. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Koizumi, Hirotaka, Maruoka, Akira and Paterson, Michael S. (1993) Consistency of natural relations on sets. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Fischer, Michael J. and Paterson, Michael S. (1992) Fishspear : a priority queue algorithm. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Gibbons, Alan (Alan M.) and Paterson, Michael S. (1992) Dense edge-disjoint embedding of binary trees in the mesh. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. and Zwick, Uri (1992) Shallow multiplication circuits and wise financial investments. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Zwick, Uri and Paterson, Michael S. (1991) The memory game. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. and Zwick, Uri (1991) Shrinkage of de Morgan formulae under restriction. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. and Zwick, Uri (1990) Shallow multiplication circuits. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S., Pippenger, Nicholas and Zwick, Uri (1990) Optimal carry save networks. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Paterson, Michael S. and Yao, F. Frances (1990) Optimal binary space partitions for orthogonal objects. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Paterson, Michael S. and Zwick, Uri (1990) Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. and Yao, F. Frances (1989) Binary partitions with applications to hidden-surface removal and solid modelling. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Paterson, Michael S. and Razborov, Alexander (1988) The set of minimal braids is co-NP-complete. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

McColl, William Finlay and Paterson, Michael S. (1988) Planar acyclic computation. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Yao, F. Frances, Dobkin, David P., Edelsbrunner, Herbert and Paterson, Michael S. (1988) Partitioning space for range queries. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Paterson, Michael S. (1987) Improved sorting networks with O(log n) depth. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Paterson, Michael S. (1986) Universal chains and wiring layouts. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Daykin, D. E., Daykin, J. W. and Paterson, Michael S. (1983) On log concavity for order-preserving and order-non-reversing maps of partial orders. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Munro, J. Ian and Paterson, Michael S. (1978) Selection and sorting with limited storage. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Paterson, Michael S. (1976) New bounds for formula size. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Valiant, Leslie and Paterson, Michael S. (1975) Circuit size is nonlinear in depth. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

McColl, William Finlay and Paterson, Michael S. (1975) The depth of all Boolean functions. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Schönhage, Arnold, Paterson, Michael S. and Pippenger, Nicholas (1975) Finding the median. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Paterson, Michael S. (1974) Complexity of monotone networks for Boolean matrix product. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)