| 2021 | ICALP | Haystack Hunting Hints and Locker Room Communication. | Artur Czumaj, George Kontogeorgiou, Mike Paterson |
| 2020 | AAAI | Convergence of Opinion Diffusion is PSPACE-Complete. | Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini |
| 2014 | SODA | Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. | Thomas Dueholm Hansen, Mike Paterson, Uri Zwick |
| 2009 | AAIM | Power Indices in Spanning Connectivity Games. | Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani |
| 2008 | ICALP | Polynomial-Time Construction of Linear Network Coding. | Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita |
| 2008 | SODA | Maximum overhang. | Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick |
| 2008 | WALCOM | Multi-commodity Source Location Problems and Price of Greed. | Hiro Ito, Mike Paterson, Kenya Sugihara |
| 2006 | ICALP | On Counting Homomorphisms to Directed Acyclic Graphs. | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson |
| 2006 | SODA | A deterministic subexponential algorithm for solving parity games. | Marcin Jurdzinski, Mike Paterson, Uri Zwick |
| 2006 | SODA | Overhang. | Mike Paterson, Uri Zwick |
| 2004 | FOCS | trong Spatial Mixing for Lattice Graphs with Fewer Colours. | Leslie Ann Goldberg, Russell A. Martin, Mike Paterson |
| 2004 | LATIN | Analysis of Scheduling Algorithms for Proportionate Fairness. | Mike Paterson |
| 2003 | SPAA | A proportionate fair scheduling rule with good worst-case performance. | Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson |
| 2002 | STOC | The complexity of choosing an H-colouring (nearly) uniformly at random. | Leslie Ann Goldberg, Steven Kelk, Mike Paterson |
| 2000 | ICALP | Tight Size Bounds for Packet Headers in Narrow Meshes. | Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson |
| 2000 | ICALP | A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. | Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson |
| 2000 | MFCS | A Family of NFA's Which Need 2 | Kazuo Iwama, Akihiro Matsuura, Mike Paterson |
| 2000 | SODA | Communication complexity of document exchange. | Graham Cormode, Mike Paterson, Sleyman Cenk Sahinalp, Uzi Vishkin |
| 1999 | SODA | The Complexity of Gene Placement. | Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Sleyman Cenk Sahinalp, Elizabeth Sweedyk |
| 1999 | STOC | Compact Grid Layouts of Multi-Level Networks. | S. Muthukrishnan, Mike Paterson, Sleyman Cenk Sahinalp, Torsten Suel |
| 1998 | SODA | On Approximating Rectangle Tiling and Packing. | Sanjeev Khanna, S. Muthukrishnan, Mike Paterson |
| 1998 | SPAA | Layout of the Batcher Bitonic Sorter (Extended Abstract). | Shimon Even, S. Muthukrishnan, Mike Paterson, Sleyman Cenk Sahinalp |
| 1998 | SIROCCO | On permutation communications in all-optical rings. | Mike Paterson, Heiko Schrder, Ondrej Skora, Imrich Vrto |
| 1997 | CPM | On Weak Circular Squares in Binary Words. | Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson |
| 1997 | SODA | Better Approximation Guarantees for Job-shop Scheduling. | Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk |
| 1996 | ICALP | On the Complexity of String Folding. | Mike Paterson, Teresa M. Przytycka |
| 1996 | SODA | On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). | Richa Agarwala, Vineet Bafna, Martin Farach, Babu O. Narayanan, Mike Paterson, Mikkel Thorup |
| 1995 | COCOON | The Complexity of Mean Payoff Games. | Uri Zwick, Mike Paterson |
| 1995 | FOCS | Lower Bounds for Monotone Span Programs. | Amos Beimel, Anna Gl, Mike Paterson |
| 1995 | FOCS | Contention Resolution with Bounded Delay. | Mike Paterson, Aravind Srinivasan |
| 1994 | MFCS | Longest Common Subsequences. | Mike Paterson, Vlado Danck |
| 1994 | STACS | Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. | Vlado Danck, Mike Paterson |
| 1993 | ESA | Evolution of an Algorithm. | Mike Paterson |
| 1992 | FOCS | The Asymptotic Complexity of Merging Networks | Peter Bro Miltersen, Mike Paterson, Jun Tarui |
| 1992 | ICALP | On Nearest-Neighbor Graphs. | Mike Paterson, F. Frances Yao |
| 1992 | ISAAC | Boolean Circuit Complexity. | Mike Paterson |
| 1992 | STOC | Shallow Multiplication Circuits and Wise Financial Investments | Mike Paterson, Uri Zwick |
| 1992 | SPAA | Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. | Alan Gibbons, Mike Paterson |
| 1991 | FOCS | Shrinkage of de~Morgan formulae under restriction | Mike Paterson, Uri Zwick |
| 1991 | WADS | The MINSUMCUT Problem. | Josep Daz, Alan Gibbons, Mike Paterson, Jacobo Torn |
| 1990 | FOCS | Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions | Mike Paterson, Nicholas Pippenger, Uri Zwick |
| 1990 | SODA | Optimal Binary Space Partitions for Orthogonal Objects. | Mike Paterson, F. Frances Yao |
| 1985 | FOCS | Dynamic Monotone Priorities on Planar Sets (Extended Abstract) | Michael J. Fischer, Mike Paterson |
| 1984 | FOCS | Fishspear: A Priority Queue Algorithm (Extended Abstract) | Michael J. Fischer, Mike Paterson |
| 1983 | PODS | Impossibility of Distributed Consensus with One Faulty Process. | Michael J. Fischer, Nancy A. Lynch, Mike Paterson |
| 1981 | STOC | Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) | Mike Paterson, Walter L. Ruzzo, Lawrence Snyder |
| 1980 | STOC | Optimal Tree Layout (Preliminary Version) | Michael J. Fischer, Mike Paterson |
| 1978 | FOCS | Selection and Sorting with Limited Storage | J. Ian Munro, Mike Paterson |
| 1976 | STOC | Linear Unification | Mike Paterson, Mark N. Wegman |
| 1975 | STOC | Lower Bounds on the Size of Boolean Formulas: Preliminary Report | Michael J. Fischer, Albert R. Meyer, Mike Paterson |
| 1974 | STOC | Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract) | Ronald V. Book, Maurice Nivat, Mike Paterson |
| 1971 | FOCS | Optimal Algorithms for Parallel Polynomial Evaluation | J. Ian Munro, Mike Paterson |
| 1971 | FOCS | Bounds on the Evaluation Time for Rational Polynomials | Mike Paterson, Larry J. Stockmeyer |
| 1970 | FOCS | Tape-Bounds for Time-Bounded Turing Machines | Mike Paterson |