On Formalised Computer Programs. - David C. Luckham; David Michael Ritchie Park; Mike Paterson (J. Comput. Syst. Sci., 1970)

Bounds on the Evaluation Time for Rational Polynomials - Mike Paterson; Larry J. Stockmeyer (SWAT, 1971)

Decision problems in computational models. - Mike Paterson (International Sympoisum on Theoretical Programming, 1972)

Tape Bounds for Time-Bounded Turing Machines. - Mike Paterson (J. Comput. Syst. Sci., 1972)

Optimal Algorithms for Parallel Polynomial Evaluation. - J. Ian Munro; Mike Paterson (J. Comput. Syst. Sci., 1973)

On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. - Mike Paterson; Larry J. Stockmeyer (SIAM J. Comput., 1973)

A note on disjunctive form tautologies. - M. Bauer; D. Brand; Michael J. Fischer; Albert R. Meyer; Mike Paterson (SIGACT News, 1973)

Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract) - Ronald V. Book; Maurice Nivat; Mike Paterson (STOC, 1974)

Reversal-Bounded Acceptors and Intersections of Linear Languages. - Ronald V. Book; Maurice Nivat; Mike Paterson (SIAM J. Comput., 1974)

Lower Bounds on the Size of Boolean Formulas: Preliminary Report - Michael J. Fischer; Albert R. Meyer; Mike Paterson (STOC, 1975)

Deterministic One-Counter Automata. - Leslie G. Valiant; Mike Paterson (J. Comput. Syst. Sci., 1975)

Complexity of Monotone Networks for Boolean Matrix Product. - Mike Paterson (Theor. Comput. Sci., 1975)

Finding the Median. - Arnold Schönhage; Mike Paterson; Nicholas Pippenger (J. Comput. Syst. Sci., 1976)

Circuit Size is Nonlinear in Depth. - Mike Paterson; Leslie G. Valiant (Theor. Comput. Sci., 1976)

New bounds on formula size. - Mike Paterson (Theoretical Computer Science, 1977)

The Depth of All Boolean Functions. - William F. McColl; Mike Paterson (SIAM J. Comput., 1977)

Linear Unification. - Mike Paterson; Mark N. Wegman (J. Comput. Syst. Sci., 1978)

The linear postman: a message-forwarding algorithm using sequential storage. - Mike Paterson (Algorithms in Modern Mathematics and Computer Science, 1979)

Optimal Tree Layout (Preliminary Version) - Michael J. Fischer; Mike Paterson (STOC, 1980)

A Faster Algorithm Computing String Edit Distances. - William J. Masek; Mike Paterson (J. Comput. Syst. Sci., 1980)

Asymtotically Optimal Circuit for a Storage Access Function. - Peter Klein; Mike Paterson (IEEE Trans. Computers, 1980)

Selection and Sorting with Limited Storage. - J. Ian Munro; Mike Paterson (Theor. Comput. Sci., 1980)

Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) - Mike Paterson; Walter L. Ruzzo; Lawrence Snyder 001 (STOC, 1981)

Optimal Packing and Covering in the Plane are NP-Complete. - Robert J. Fowler; Mike Paterson; Steven L. Tanimoto (Inf. Process. Lett., 1981)

Propositional Dynamic Logic is Weaker without Tests. - Francine Berman; Mike Paterson (Theor. Comput. Sci., 1981)

Efficient Parallel Algorithms for Linear Recurrence Computation. - Albert G. Greenberg; Richard E. Ladner; Mike Paterson; Zvi Galil (Inf. Process. Lett., 1982)

Omega(n log n) Lower Bounds on Length of Boolean Formulas. - Michael J. Fischer; Albert R. Meyer; Mike Paterson (SIAM J. Comput., 1982)

Storage Requirements for Fair Scheduling. - Michael J. Fischer; Mike Paterson (Inf. Process. Lett., 1983)

Fishspear: A Priority Queue Algorithm (Extended Abstract) - Michael J. Fischer; Mike Paterson (FOCS, 1984)

Undecidability of PDL with L={a^(2i)|i>=0}. - David Harel; Mike Paterson (J. Comput. Syst. Sci., 1984)

Dynamic Monotone Priorities on Planar Sets (Extended Abstract) - Michael J. Fischer; Mike Paterson (FOCS, 1985)

Impossibility of Distributed Consensus with One Faulty Process - Michael J. Fischer; Nancy A. Lynch; Mike Paterson (J. ACM, 1985)

Nearly Optimal Hierarchies for Network and Formula Size. - Mike Paterson; Ingo Wegener (Acta Informatica, 1986)

Point Retrieval for Polygons. - Mike Paterson; F. Frances Yao (J. Algorithms, 1986)

The Planar Realization of Boolean Functions. - William F. McColl; Mike Paterson (Inf. Process. Lett., 1987)

Universal Chains and Wiring Layouts. - Mike Paterson (SIAM J. Discret. Math., 1988)

Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling. - Mike Paterson; F. Frances Yao (SCG, 1989)

Partitioning Space for Range Queries. - F. Frances Yao; David P. Dobkin; Herbert Edelsbrunner; Mike Paterson (SIAM J. Comput., 1989)

Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions - Mike Paterson; Nicholas Pippenger; Uri Zwick (FOCS, 1990)

Computing Euclidean Maximum Spanning Trees. - Clyde L. Monma; Mike Paterson; Subhash Suri; F. Frances Yao (Algorithmica, 1990)

Improved Sorting Networks with O(log N) Depth. - Mike Paterson (Algorithmica, 1990)

Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling. - Mike Paterson; F. Frances Yao (Discret. Comput. Geom., 1990)

The MINSUMCUT Problem. - Josep Díaz; Alan Gibbons; Mike Paterson; Jacobo Torán (WADS, 1991)

The Set of Minimal Braids is co-NP-Complete. - Mike Paterson; Alexander A. Razborov (J. Algorithms, 1991)

Planar Acyclic Computation - William F. McColl; Mike Paterson; Brian H. Bowditch (Inf. Comput., 1991)

On Nearest-Neighbor Graphs. - Mike Paterson; F. Frances Yao (ICALP, 1992)

Boolean Circuit Complexity. - Mike Paterson (ISAAC, 1992)

Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. - Alan Gibbons; Mike Paterson (SPAA, 1992)

Shallow Multiplication Circuits and Wise Financial Investments - Mike Paterson; Uri Zwick (STOC, 1992)

Optimal Binary Space Partitions for Orthogonal Objects. - Mike Paterson; F. Frances Yao (J. Algorithms, 1992)

Evolution of an Algorithm. - Mike Paterson (ESA, 1993)

Which Patterns are Hard to Find? - Richard Cole 001; Ramesh Hariharan; Mike Paterson; Uri Zwick (ISTCS, 1993)

Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. - Mike Paterson; Uri Zwick (Comput. Complex., 1993)

A Short Proof of the Dilation of a Toroidal Mesh in a Path. - Mike Paterson; Heiko Schröder 001; Ondrej Sýkora; Imrich Vrto (Inf. Process. Lett., 1993)

Shrinkage of de Morgan Formulae under Restriction. - Mike Paterson; Uri Zwick (Random Struct. Algorithms, 1993)

The Memory Game. - Uri Zwick; Mike Paterson (Theor. Comput. Sci., 1993)

Longest Common Subsequences. - Mike Paterson; Vlado Dancík (MFCS, 1994)

Fishspear: A Priority Queue Algorithm. - Michael J. Fischer; Mike Paterson (J. ACM, 1994)

David Michael Ritchie Park (1935-1990) in Memoriam. - Mike Paterson (Theor. Comput. Sci., 1994)

The Complexity of Mean Payoff Games. - Uri Zwick; Mike Paterson (COCOON, 1995)

Contention Resolution with Bounded Delay. - Mike Paterson; Aravind Srinivasan (FOCS, 1995)

Looking for MUM and DAD: Text-Text Comparisons Do Help. - Mike Paterson; Shlomit Tassa; Uri Zwick (FSTTCS, 1995)

PIk Mass Production and an Optimal Circuit for the Neciporuk Slice. - Alain P. Hiltgen; Mike Paterson (Comput. Complex., 1995)

Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. - Vlado Dancík; Mike Paterson (Random Struct. Algorithms, 1995)

Tighter Lower Bounds on the Exact Complexity of String Matching. - Richard Cole 001; Ramesh Hariharan; Mike Paterson; Uri Zwick (SIAM J. Comput., 1995)

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). - Richa Agarwala; Vineet Bafna; Martin Farach; Babu O. Narayanan; Mike Paterson; Mikkel Thorup (SODA, 1996)

Progress in Selection. - Mike Paterson (SWAT, 1996)

On the Complexity of String Folding. - Mike Paterson; Teresa M. Przytycka (Discret. Appl. Math., 1996)

The Asymptotic Complexity of Merging Networks. - Peter Bro Miltersen; Mike Paterson; Jun Tarui (J. ACM, 1996)

The Complexity of Mean Payoff Games on Graphs. - Uri Zwick; Mike Paterson (Theor. Comput. Sci., 1996)

On Weak Circular Squares in Binary Words. - Aviezri S. Fraenkel; Jamie Simpson; Mike Paterson (CPM, 1997)

Lower Bounds for Monotone Span Programs. - Amos Beimel; Anna Gál; Mike Paterson (Comput. Complex., 1997)

On Nearest-Neighbor Graphs. - David Eppstein; Mike Paterson; F. Frances Yao (Discret. Comput. Geom., 1997)

On permutation communications in all-optical rings. - Mike Paterson; Heiko Schröder 001; Ondrej Sýkora; Imrich Vrto (SIROCCO, 1998)

On Approximating Rectangle Tiling and Packing. - Sanjeev Khanna; S. Muthukrishnan 001; Mike Paterson (SODA, 1998)

Layout of the Batcher Bitonic Sorter (Extended Abstract). - Shimon Even; S. Muthukrishnan 001; Mike Paterson; Süleyman Cenk Sahinalp (SPAA, 1998)

Consistency of Natural Relations on Sets. - Akira Maruoka; Mike Paterson; Hirotaka Koizumi (Comb. Probab. Comput., 1998)

Compact Grid Layouts of Multi-Level Networks. - S. Muthukrishnan 001; Mike Paterson; Süleyman Cenk Sahinalp; Torsten Suel (STOC, 1999)

Optimal Layout of Edge-weighted Forests. - Michael J. Fischer; Mike Paterson (Discret. Appl. Math., 1999)

The chip in your wallet - The technology of security in smartcard chip manufacture. - Mike Paterson (Inf. Secur. Tech. Rep., 1999)

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). - Richa Agarwala; Vineet Bafna; Martin Farach; Mike Paterson; Mikkel Thorup (SIAM J. Comput., 1999)

Tight Size Bounds for Packet Headers in Narrow Meshes. - Micah Adler; Faith E. Fich; Leslie Ann Goldberg; Mike Paterson (ICALP, 2000)

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. - Leslie Ann Goldberg; Mark Jerrum; Sampath Kannan; Mike Paterson (ICALP, 2000)

A Family of NFA's Which Need 2n -alpha Deterministic States. - Kazuo Iwama; Akihiro Matsuura; Mike Paterson (MFCS, 2000)

Communication complexity of document exchange. - Graham Cormode; Mike Paterson; Süleyman Cenk Sahinalp; Uzi Vishkin (SODA, 2000)

Contention resolution with constant expected delay. - Leslie Ann Goldberg; Philip D. MacKenzie; Mike Paterson; Aravind Srinivasan (J. ACM, 2000)

Dense edge-disjoint embedding of complete binary trees in interconnection networks. - Somasundaram Ravindran; Alan Gibbons; Mike Paterson (Theor. Comput. Sci., 2000)

The Complexity of Gene Placement. - Leslie Ann Goldberg; Paul W. Goldberg; Mike Paterson; Pavel A. Pevzner; Süleyman Cenk Sahinalp; Elizabeth Sweedyk (J. Algorithms, 2001)

Better Approximation Guarantees for Job-Shop Scheduling. - Leslie Ann Goldberg; Mike Paterson; Aravind Srinivasan; Elizabeth Sweedyk (SIAM J. Discret. Math., 2001)

The complexity of choosing an H-colouring (nearly) uniformly at random. - Leslie Ann Goldberg; Steven Kelk; Mike Paterson (STOC, 2002)

Permutation Communication in All-Optical Rings. - Mike Paterson; Heiko Schröder 001; Ondrej Sýkora; Imrich Vrto (Parallel Process. Lett., 2002)

A proportionate fair scheduling rule with good worst-case performance. - Micah Adler; Petra Berenbrink; Tom Friedetzky; Leslie Ann Goldberg; Paul W. Goldberg; Mike Paterson (SPAA, 2003)

The computational complexity of two-state spin systems. - Leslie Ann Goldberg; Mark Jerrum; Mike Paterson (Random Struct. Algorithms, 2003)

A family of NFAs which need 2n- deterministic states. - Kazuo Iwama; Akihiro Matsuura; Mike Paterson (Theor. Comput. Sci., 2003)

trong Spatial Mixing for Lattice Graphs with Fewer Colours. - Leslie Ann Goldberg; Russell A. Martin; Mike Paterson (FOCS, 2004)

Analysis of Scheduling Algorithms for Proportionate Fairness. - Mike Paterson (LATIN, 2004)

Random sampling of 3-colorings in Z2. - Leslie Ann Goldberg; Russell A. Martin; Mike Paterson (Random Struct. Algorithms, 2004)

A bound on the capacity of backoff and acknowledgment-based protocols. - Leslie Ann Goldberg; Mark Jerrum; Sampath Kannan; Mike Paterson (SIAM J. Comput., 2004)

The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random. - Leslie Ann Goldberg; Steven Kelk; Mike Paterson (SIAM J. Comput., 2004)

On counting homomorphisms to directed acyclic graphs - Martin E. Dyer; Leslie Ann Goldberg; Mike Paterson (Electron. Colloquium Comput. Complex., 2005)

Strong Spatial Mixing with Fewer Colors for Lattice Graphs. - Leslie Ann Goldberg; Russell A. Martin; Mike Paterson (SIAM J. Comput., 2005)

Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2. - Leslie Ann Goldberg; Markus Jalsenius; Russell Martin; Mike Paterson (LMS J. Comput. Math., 2006)

Polynomial-Time Construction of Linear Network Coding. - Kazuo Iwama; Harumichi Nishimura; Mike Paterson; Rudy Raymond; Shigeru Yamashita (ICALP (1), 2008)

Computing voting power in easy weighted voting games - Haris Aziz 001; Mike Paterson (CoRR, 2008)

A Deterministic Subexponential Algorithm for Solving Parity Games. - Marcin Jurdzinski; Mike Paterson; Uri Zwick (SIAM J. Comput., 2008)

Power Indices in Spanning Connectivity Games. - Haris Aziz 001; Oded Lachish; Mike Paterson; Rahul Savani (AAIM, 2009)

False name manipulations in weighted voting games: splitting, merging and annexation. - Haris Aziz 001; Mike Paterson (AAMAS (1), 2009)

Wiretapping a Hidden Network. - Haris Aziz 001; Oded Lachish; Mike Paterson; Rahul Savani (WINE, 2009)

Spanning connectivity games - Haris Aziz 001; Oded Lachish; Mike Paterson; Rahul Savani (CoRR, 2009)

The Multi-Commodity Source Location Problems and the Price of Greed. - Hiro Ito; Mike Paterson; Kenya Sugihara (J. Graph Algorithms Appl., 2009)

Maximum Overhang. - Mike Paterson; Yuval Peres; Mikkel Thorup; Peter Winkler 001; Uri Zwick (Am. Math. Mon., 2009)

Overhang. - Mike Paterson; Uri Zwick (Am. Math. Mon., 2009)

False-Name Manipulations in Weighted Voting Games. - Haris Aziz 001; Yoram Bachrach; Edith Elkind; Mike Paterson (J. Artif. Intell. Res., 2011)

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. - Thomas Dueholm Hansen; Mike Paterson; Uri Zwick (SODA, 2014)

Maximizing the area of intersection of rectangles. - David B. A. Epstein; Mike Paterson (CoRR, 2017)

Convergence of Opinion Diffusion is PSPACE-Complete. - Dmitry Chistikov 001; Grzegorz Lisowski; Mike Paterson; Paolo Turrini (AAAI, 2020)

Globe-hopping. - Dmitry Chistikov 001; Olga Goulko; Adrian Kent; Mike Paterson (CoRR, 2020)

Combinatorial Communication in the Locker Room. - Artur Czumaj; George Kontogeorgiou; Mike Paterson (CoRR, 2020)

Bounded Hanoi. - Kazuo Iwama; Mike Paterson (Am. Math. Mon., 2022)

Haystack hunting hints and locker room communication. - Artur Czumaj; George Kontogeorgiou; Mike Paterson (Random Struct. Algorithms, 2023)

Learning a Social Network by Influencing Opinions. - Dmitry Chistikov 001; Luisa Estrada; Mike Paterson; Paolo Turrini (AAMAS, 2024)

Variance Dichotomy in Feature Spaces of Facial Recognition Systems is a Weak Defense against Simple Weight Manipulation Attacks. - Matthew Bowditch; Mike Paterson; Matthias Englert; Ranko Lazic 001 (Trans. Mach. Learn. Res., 2025)