Mike Paterson

According to our database, Mike Paterson authored at least 120 papers between 1970 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2022

Bounded Hanoi.

Kazuo Iwama, Mike Paterson

Am. Math. Mon., 2022

2021

Haystack Hunting Hints and Locker Room Communication.

Artur Czumaj, George Kontogeorgiou, Mike Paterson

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Combinatorial Communication in the Locker Room.

Artur Czumaj, George Kontogeorgiou, Mike Paterson

CoRR, 2020

Globe-hopping.

Dmitry Chistikov, Olga Goulko, Adrian Kent, Mike Paterson

CoRR, 2020

Convergence of Opinion Diffusion is PSPACE-Complete.

Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2017

Maximizing the area of intersection of rectangles.

David B. A. Epstein, Mike Paterson

CoRR, 2017

2014

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes.

Thomas Dueholm Hansen, Mike Paterson, Uri Zwick

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2011

False-Name Manipulations in Weighted Voting Games.

Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson

J. Artif. Intell. Res., 2011

2009

Overhang.

Mike Paterson, Uri Zwick

Am. Math. Mon., 2009

Maximum Overhang.

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick

Am. Math. Mon., 2009

The Multi-Commodity Source Location Problems and the Price of Greed.

Hiro Ito, Mike Paterson, Kenya Sugihara

J. Graph Algorithms Appl., 2009

Spanning connectivity games

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani

CoRR, 2009

Wiretapping a Hidden Network.

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

False name manipulations in weighted voting games: splitting, merging and annexation.

Haris Aziz, Mike Paterson

Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), 2009

Power Indices in Spanning Connectivity Games.

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani

Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008

A Deterministic Subexponential Algorithm for Solving Parity Games.

Marcin Jurdzinski, Mike Paterson, Uri Zwick

SIAM J. Comput., 2008

Computing voting power in easy weighted voting games

Haris Aziz, Mike Paterson

CoRR, 2008

Polynomial-Time Construction of Linear Network Coding.

Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

On counting homomorphisms to directed acyclic graphs.

Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson

J. ACM, 2007

2006

Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z².

Leslie Ann Goldberg, Markus Jalsenius, Russell Martin, Mike Paterson

LMS J. Comput. Math., 2006

2005

Strong Spatial Mixing with Fewer Colors for Lattice Graphs.

Leslie Ann Goldberg, Russell A. Martin, Mike Paterson

SIAM J. Comput., 2005

2004

The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random.

Leslie Ann Goldberg, Steven Kelk, Mike Paterson

SIAM J. Comput., 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

Random sampling of 3-colorings in Z².

Leslie Ann Goldberg, Russell A. Martin, Mike Paterson

Random Struct. Algorithms, 2004

Analysis of Scheduling Algorithms for Proportionate Fairness.

Mike Paterson

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

trong Spatial Mixing for Lattice Graphs with Fewer Colours.

Leslie Ann Goldberg, Russell A. Martin, Mike Paterson

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

A family of NFAs which need 2n- deterministic states.

Kazuo Iwama, Akihiro Matsuura, Mike Paterson

Theor. Comput. Sci., 2003

The computational complexity of two-state spin systems.

Leslie Ann Goldberg, Mark Jerrum, Mike Paterson

Random Struct. Algorithms, 2003

A proportionate fair scheduling rule with good worst-case performance.

Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

2002

Permutation Communication in All-Optical Rings.

Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto

Parallel Process. Lett., 2002

The complexity of choosing an H-colouring (nearly) uniformly at random.

Leslie Ann Goldberg, Steven Kelk, Mike Paterson

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

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 Gene Placement.

Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk

J. Algorithms, 2001

2000

Dense edge-disjoint embedding of complete binary trees in interconnection networks.

Somasundaram Ravindran, Alan Gibbons, Mike Paterson

Theor. Comput. Sci., 2000

Contention resolution with constant expected delay.

Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan

J. ACM, 2000

Communication complexity of document exchange.

Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A Family of NFA's Which Need 2ⁿ -<i>alpha</i> Deterministic States.

Kazuo Iwama, Akihiro Matsuura, Mike Paterson

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.

Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Tight Size Bounds for Packet Headers in Narrow Meshes.

Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

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

The chip in your wallet - The technology of security in smartcard chip manufacture.

Mike Paterson

Inf. Secur. Tech. Rep., 1999

Optimal Layout of Edge-weighted Forests.

Michael J. Fischer, Mike Paterson

Discret. Appl. Math., 1999

Compact Grid Layouts of Multi-Level Networks.

S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Consistency of Natural Relations on Sets.

Akira Maruoka, Mike Paterson, Hirotaka Koizumi

Comb. Probab. Comput., 1998

Layout of the Batcher Bitonic Sorter (Extended Abstract).

Shimon Even, S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp

Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998

On Approximating Rectangle Tiling and Packing.

Sanjeev Khanna, S. Muthukrishnan, Mike Paterson

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

On permutation communications in all-optical rings.

Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto

Proceedings of the SIROCCO'98, 1998

1997

On Nearest-Neighbor Graphs.

David Eppstein, Mike Paterson, F. Frances Yao

Discret. Comput. Geom., 1997

Lower Bounds for Monotone Span Programs.

Amos Beimel, Anna Gál, Mike Paterson

Comput. Complex., 1997

On Weak Circular Squares in Binary Words.

Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson

Proceedings of the Combinatorial Pattern Matching, 8th Annual Symposium, 1997

1996

The Complexity of Mean Payoff Games on Graphs.

Uri Zwick, Mike Paterson

Theor. Comput. Sci., 1996

The Asymptotic Complexity of Merging Networks.

Peter Bro Miltersen, Mike Paterson, Jun Tarui

J. ACM, 1996

On the Complexity of String Folding.

Mike Paterson, Teresa M. Przytycka

Discret. Appl. Math., 1996

Progress in Selection.

Mike Paterson

Proceedings of the Algorithm Theory, 1996

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).

Richa Agarwala, Vineet Bafna, Martin Farach, Babu O. Narayanan, Mike Paterson, Mikkel Thorup

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995

Tighter Lower Bounds on the Exact Complexity of String Matching.

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick

SIAM J. Comput., 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

PI_k Mass Production and an Optimal Circuit for the Neciporuk Slice.

Alain P. Hiltgen, Mike Paterson

Comput. Complex., 1995

Looking for MUM and DAD: Text-Text Comparisons Do Help.

Mike Paterson, Shlomit Tassa, Uri Zwick

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Contention Resolution with Bounded Delay.

Mike Paterson, Aravind Srinivasan

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

The Complexity of Mean Payoff Games.

Uri Zwick, Mike Paterson

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994

David Michael Ritchie Park (1935-1990) in Memoriam.

Mike Paterson

Theor. Comput. Sci., 1994

Fishspear: A Priority Queue Algorithm.

Michael J. Fischer, Mike Paterson

J. ACM, 1994

Longest Common Subsequences.

Mike Paterson, Vlado Dancík

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

1993

The Memory Game.

Uri Zwick, Mike Paterson

Theor. Comput. Sci., 1993

Shrinkage of de Morgan Formulae under Restriction.

Mike Paterson, Uri Zwick

Random Struct. Algorithms, 1993

A Short Proof of the Dilation of a Toroidal Mesh in a Path.

Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto

Inf. Process. Lett., 1993

Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication.

Mike Paterson, Uri Zwick

Comput. Complex., 1993

Which Patterns are Hard to Find?

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Evolution of an Algorithm.

Mike Paterson

Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992

Optimal Binary Space Partitions for Orthogonal Objects.

Mike Paterson, F. Frances Yao

J. Algorithms, 1992

Shallow Multiplication Circuits and Wise Financial Investments

Mike Paterson, Uri Zwick

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Dense Edge-Disjoint Embedding of Binary Trees in the Mesh.

Alan Gibbons, Mike Paterson

Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Boolean Circuit Complexity.

Mike Paterson

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

On Nearest-Neighbor Graphs.

Mike Paterson, F. Frances Yao

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991

Planar Acyclic Computation

William F. McColl, Mike Paterson, Brian H. Bowditch

Inf. Comput., February, 1991

The Set of Minimal Braids is co-NP-Complete.

Mike Paterson, Alexander A. Razborov

J. Algorithms, 1991

The MINSUMCUT Problem.

Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán

Proceedings of the Algorithms and Data Structures, 1991

1990

Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling.

Mike Paterson, F. Frances Yao

Discret. Comput. Geom., 1990

Improved Sorting Networks with O(log N) Depth.

Mike Paterson

Algorithmica, 1990

Computing Euclidean Maximum Spanning Trees.

Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao

Algorithmica, 1990

Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions

Mike Paterson, Nicholas Pippenger, Uri Zwick

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Partitioning Space for Range Queries.

F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, Mike Paterson

SIAM J. Comput., 1989

Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling.

Mike Paterson, F. Frances Yao

Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988

Universal Chains and Wiring Layouts.

Mike Paterson

SIAM J. Discret. Math., 1988

1987

The Planar Realization of Boolean Functions.

William F. McColl, Mike Paterson

Inf. Process. Lett., 1987

1986

Point Retrieval for Polygons.

Mike Paterson, F. Frances Yao

J. Algorithms, 1986

Nearly Optimal Hierarchies for Network and Formula Size.

Mike Paterson, Ingo Wegener

Acta Informatica, 1986

1985

Impossibility of Distributed Consensus with One Faulty Process

Michael J. Fischer, Nancy A. Lynch, Mike Paterson

J. ACM, April, 1985

Dynamic Monotone Priorities on Planar Sets (Extended Abstract)

Michael J. Fischer, Mike Paterson

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

Undecidability of PDL with L={a^(2i)|i>=0}.

David Harel, Mike Paterson

J. Comput. Syst. Sci., 1984

Fishspear: A Priority Queue Algorithm (Extended Abstract)

Michael J. Fischer, Mike Paterson

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Storage Requirements for Fair Scheduling.

Michael J. Fischer, Mike Paterson

Inf. Process. Lett., 1983

1982

Omega(n log n) Lower Bounds on Length of Boolean Formulas.

Michael J. Fischer, Albert R. Meyer, Mike Paterson

SIAM J. Comput., 1982

Efficient Parallel Algorithms for Linear Recurrence Computation.

Albert G. Greenberg, Richard E. Ladner, Mike Paterson, Zvi Galil

Inf. Process. Lett., 1982

1981

Propositional Dynamic Logic is Weaker without Tests.

Francine Berman, Mike Paterson

Theor. Comput. Sci., 1981

Optimal Packing and Covering in the Plane are NP-Complete.

Robert J. Fowler, Mike Paterson, Steven L. Tanimoto

Inf. Process. Lett., 1981

Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract)

Mike Paterson, Walter L. Ruzzo, Lawrence Snyder

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980

Selection and Sorting with Limited Storage.

J. Ian Munro, Mike Paterson

Theor. Comput. Sci., 1980

Asymtotically Optimal Circuit for a Storage Access Function.

Peter Klein, Mike Paterson

IEEE Trans. Computers, 1980

A Faster Algorithm Computing String Edit Distances.

William J. Masek, Mike Paterson

J. Comput. Syst. Sci., 1980

Optimal Tree Layout (Preliminary Version)

Michael J. Fischer, Mike Paterson

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979

The linear postman: a message-forwarding algorithm using sequential storage.

Mike Paterson

Proceedings of the Algorithms in Modern Mathematics and Computer Science, 1979

1978

Linear Unification.

Mike Paterson, Mark N. Wegman

J. Comput. Syst. Sci., 1978

1977

The Depth of All Boolean Functions.

William F. McColl, Mike Paterson

SIAM J. Comput., 1977

New bounds on formula size.

Mike Paterson

Proceedings of the Theoretical Computer Science, 1977

1976

Circuit Size is Nonlinear in Depth.

Mike Paterson, Leslie G. Valiant

Theor. Comput. Sci., 1976

Finding the Median.

Arnold Schönhage, Mike Paterson, Nicholas Pippenger

J. Comput. Syst. Sci., 1976

1975

Complexity of Monotone Networks for Boolean Matrix Product.

Mike Paterson

Theor. Comput. Sci., 1975

Deterministic One-Counter Automata.

Leslie G. Valiant, Mike Paterson

J. Comput. Syst. Sci., 1975

Lower Bounds on the Size of Boolean Formulas: Preliminary Report

Michael J. Fischer, Albert R. Meyer, Mike Paterson

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974

Reversal-Bounded Acceptors and Intersections of Linear Languages.

Ronald V. Book, Maurice Nivat, Mike Paterson

SIAM J. Comput., 1974

Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract)

Ronald V. Book, Maurice Nivat, Mike Paterson

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973

A note on disjunctive form tautologies.

M. Bauer, D. Brand, Michael J. Fischer, Albert R. Meyer, Mike Paterson

SIGACT News, 1973

On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials.

Mike Paterson, Larry J. Stockmeyer

SIAM J. Comput., 1973

Optimal Algorithms for Parallel Polynomial Evaluation.

J. Ian Munro, Mike Paterson

J. Comput. Syst. Sci., 1973

1972

Tape Bounds for Time-Bounded Turing Machines.

Mike Paterson

J. Comput. Syst. Sci., 1972

Decision problems in computational models.

Mike Paterson

Proceedings of the International Sympoisum on Theoretical Programming, 1972

1971

Bounds on the Evaluation Time for Rational Polynomials

Mike Paterson, Larry J. Stockmeyer

Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

1970

On Formalised Computer Programs.

David C. Luckham, David Michael Ritchie Park, Mike Paterson

J. Comput. Syst. Sci., 1970