Mike Paterson

Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson: False-Name Manipulations in Weighted Voting Games. J. Artif. Intell. Res. (JAIR) 40: 57-93 (2011)

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

Mike Paterson, Uri Zwick: Overhang. The American Mathematical Monthly 116(1): 19-44 (2009)

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick: Maximum Overhang. The American Mathematical Monthly 116(9): 763-787 (2009)

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani: Power Indices in Spanning Connectivity Games. AAIM 2009: 55-67

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

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani: Wiretapping a Hidden Network. WINE 2009: 438-446

Haris Aziz, Mike Paterson: False name manipulations in weighted voting games: splitting, merging and annexation. CoRR abs/0905.3348 (2009)

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani: Spanning connectivity games. CoRR abs/0906.3643 (2009)

Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani: Wiretapping a hidden network. CoRR abs/0909.5293 (2009)

Marcin Jurdzinski, Mike Paterson, Uri Zwick: A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM J. Comput. 38(4): 1519-1532 (2008)

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

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick: Maximum overhang. SODA 2008: 756-765

Hiro Ito, Mike Paterson, Kenya Sugihara: Multi-commodity Source Location Problems and Price of Greed. WALCOM 2008: 169-179

Haris Aziz, Mike Paterson: Computing voting power in easy weighted voting games. CoRR abs/0811.2497 (2008)

Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs. J. ACM 54(6) (2007)

Bo Chen, Mike Paterson, Guochuan Zhang (Eds.): Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers. Lecture Notes in Computer Science 4614, Springer 2007, isbn 978-3-540-74449-8

Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) 2006: 38-49

Marcin Jurdzinski, Mike Paterson, Uri Zwick: A deterministic subexponential algorithm for solving parity games. SODA 2006: 117-123

Mike Paterson, Uri Zwick: Overhang. SODA 2006: 231-240

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

Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs. Electronic Colloquium on Computational Complexity (ECCC)(121) (2005)

Leslie Ann Goldberg, Russell A. Martin, Mike Paterson: Random sampling of 3-colorings in Z². Random Struct. Algorithms 24(3): 279-302 (2004)

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

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

Leslie Ann Goldberg, Russell A. Martin, Mike Paterson: trong Spatial Mixing for Lattice Graphs with Fewer Colours. FOCS 2004: 562-571

Mike Paterson: Analysis of Scheduling Algorithms for Proportionate Fairness. LATIN 2004: 1

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

Kazuo Iwama, Akihiro Matsuura, Mike Paterson: A family of NFAs which need 2n- deterministic states. Theor. Comput. Sci. 1-3(301): 451-462 (2003)

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

Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto: Permutation Communication in All-Optical Rings. Parallel Processing Letters 12(1): 23-29 (2002)

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

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

Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk: Better Approximation Guarantees for Job-Shop Scheduling. SIAM J. Discrete Math. 14(1): 67-92 (2001)

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

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

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

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

Kazuo Iwama, Akihiro Matsuura, Mike Paterson: A Family of NFA's Which Need 2ⁿ -alpha Deterministic States. MFCS 2000: 436-445

Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin: Communication complexity of document exchange. SODA 2000: 197-206

Mike Paterson (Ed.): Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings. Lecture Notes in Computer Science 1879, Springer 2000, isbn 3-540-41004-X

Michael J. Fischer, Mike Paterson: Optimal Layout of Edge-weighted Forests. Discrete Applied Mathematics 90(1-3): 135-159 (1999)

Mike Paterson: The chip in your wallet - The technology of security in smartcard chip manufacture. Inf. Sec. Techn. Report 4(2): 13-18 (1999)

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

Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk: The Complexity of Gene Placement. SODA 1999: 386-395

S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel: Compact Grid Layouts of Multi-Level Networks. STOC 1999: 455-463

Maxime Crochemore, Mike Paterson (Eds.): Combinatorial Pattern Matching, 10th Annual Symposium, CPM 99, Warwick University, UK, July 22-24, 1999, Proceedings. Lecture Notes in Computer Science 1645, Springer 1999, isbn 3-540-66278-2

Akira Maruoka, Mike Paterson, Hirotaka Koizumi: Consistency of Natural Relations on Sets. Combinatorics, Probability & Computing 7(3): 281-293 (1998)

Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto: On permutation communications in all-optical rings. SIROCCO 1998: 1-9

Sanjeev Khanna, S. Muthukrishnan, Mike Paterson: On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393

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

Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. Computational Complexity 6(1): 29-45 (1997)

David Eppstein, Mike Paterson, F. Frances Yao: On Nearest-Neighbor Graphs. Discrete & Computational Geometry 17(3): 263-282 (1997)

Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson: On Weak Circular Squares in Binary Words. CPM 1997: 76-82

Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk: Better Approximation Guarantees for Job-shop Scheduling. SODA 1997: 599-608

Mike Paterson, Teresa M. Przytycka: On the Complexity of String Folding. Discrete Applied Mathematics 71(1-3): 217-230 (1996)

Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996)

Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. 158(1&2): 343-359 (1996)

Mike Paterson, Teresa M. Przytycka: On the Complexity of String Folding. ICALP 1996: 658-669

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

Mike Paterson: Progress in Selection. SWAT 1996: 368-379

Alain P. Hiltgen, Mike Paterson: PI_k Mass Production and an Optimal Circuit for the Neciporuk Slice. Computational Complexity 5(2): 132-154 (1995)

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

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Tighter Lower Bounds on the Exact Complexity of String Matching. SIAM J. Comput. 24(1): 30-45 (1995)

Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games. COCOON 1995: 1-10

Mike Paterson, Aravind Srinivasan: Contention Resolution with Bounded Delay. FOCS 1995: 104-113

Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. FOCS 1995: 674-681

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

Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. Electronic Colloquium on Computational Complexity (ECCC) 2(1) (1995)

Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs. Electronic Colloquium on Computational Complexity (ECCC) 2(40) (1995)

Michael J. Fischer, Mike Paterson: Fishspear: A Priority Queue Algorithm. J. ACM 41(1): 3-30 (1994)

Mike Paterson: David Michael Ritchie Park (1935-1990) in Memoriam. Theor. Comput. Sci. 133(1): 187-200 (1994)

Mike Paterson, Vlado Dancík: Longest Common Subsequences. MFCS 1994: 127-142

Vlado Dancík, Mike Paterson: Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. STACS 1994: 669-678

Mike Paterson, Uri Zwick: Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. Computational Complexity 3: 262-291 (1993)

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

Mike Paterson, Uri Zwick: Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms 4(2): 135-150 (1993)

Uri Zwick, Mike Paterson: The Memory Game. Theor. Comput. Sci. 110(1): 169-196 (1993)

Mike Paterson: Evolution of an Algorithm. ESA 1993: 306-308

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Which Patterns are Hard to Find? ISTCS 1993: 59-68

Mike Paterson, F. Frances Yao: Optimal Binary Space Partitions for Orthogonal Objects. J. Algorithms 13(1): 99-113 (1992)

Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. FOCS 1992: 236-246

Mike Paterson, F. Frances Yao: On Nearest-Neighbor Graphs. ICALP 1992: 416-426

Mike Paterson: Boolean Circuit Complexity. ISAAC 1992: 187

Alan Gibbons, Mike Paterson: Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. SPAA 1992: 257-263

Mike Paterson, Uri Zwick: Shallow Multiplication Circuits and Wise Financial Investments. STOC 1992: 429-437

William F. McColl, Mike Paterson, B. H. Bowditch: Planar Acyclic Computation. Inf. Comput. 90(2): 178-193 (1991)

Mike Paterson, Alexander A. Razborov: The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991)

Mike Paterson, Uri Zwick: Shrinkage of de~Morgan formulae under restriction. FOCS 1991: 324-333

Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán: The MINSUMCUT Problem. WADS 1991: 65-89

Mike Paterson: Improved Sorting Networks with O(log N) Depth. Algorithmica 5(1): 65-92 (1990)

Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. Algorithmica 5(3): 407-419 (1990)

Mike Paterson, F. Frances Yao: Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling. Discrete & Computational Geometry 5: 485-503 (1990)

Mike Paterson, Nicholas Pippenger, Uri Zwick: Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions. FOCS 1990: 642-650

Mike Paterson, F. Frances Yao: Optimal Binary Space Partitions for Orthogonal Objects. SODA 1990: 100-106

Mike Paterson (Ed.): Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, July 16-20, 1990, Proceedings. Lecture Notes in Computer Science 443, Springer 1990, isbn 3-540-52826-1

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

Mike Paterson, F. Frances Yao: Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling. Symposium on Computational Geometry 1989: 23-32

Mike Paterson: Universal Chains and Wiring Layouts. SIAM J. Discrete Math. 1(1): 80-85 (1988)

Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. Symposium on Computational Geometry 1988: 241-251

William F. McColl, Mike Paterson: The Planar Realization of Boolean Functions. Inf. Process. Lett. 24(3): 165-170 (1987)

Mike Paterson, Ingo Wegener: Nearly Optimal Hierarchies for Network and Formula Size. Acta Inf. 23(2): 217-221 (1986)

Mike Paterson, F. Frances Yao: Point Retrieval for Polygons. J. Algorithms 7(3): 441-447 (1986)

Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32(2): 374-382 (1985)

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

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

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

Michael J. Fischer, Mike Paterson: Storage Requirements for Fair Scheduling. Inf. Process. Lett. 17(5): 249-250 (1983)

Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. PODS 1983: 1-7

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

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

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

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

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

William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980)

Peter Klein, Mike Paterson: Asymtotically Optimal Circuit for a Storage Access Function. IEEE Trans. Computers 29(8): 737-738 (1980)

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

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

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

Mike Paterson, Mark N. Wegman: Linear Unification. J. Comput. Syst. Sci. 16(2): 158-167 (1978)

J. Ian Munro, Mike Paterson: Selection and Sorting with Limited Storage. FOCS 1978: 253-258

William F. McColl, Mike Paterson: The Depth of All Boolean Functions. SIAM J. Comput. 6(2): 373-380 (1977)

Mike Paterson: New bounds on formula size. Theoretical Computer Science 1977: 17-26

Arnold Schönhage, Mike Paterson, Nicholas Pippenger: Finding the Median. J. Comput. Syst. Sci. 13(2): 184-199 (1976)

Mike Paterson, Leslie G. Valiant: Circuit Size is Nonlinear in Depth. Theor. Comput. Sci. 2(3): 397-400 (1976)

Mike Paterson, Mark N. Wegman: Linear Unification. STOC 1976: 181-186

Leslie G. Valiant, Mike Paterson: Deterministic One-Counter Automata. J. Comput. Syst. Sci. 10(3): 340-350 (1975)

Mike Paterson: Complexity of Monotone Networks for Boolean Matrix Product. Theor. Comput. Sci. 1(1): 13-20 (1975)

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

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

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

J. Ian Munro, Mike Paterson: Optimal Algorithms for Parallel Polynomial Evaluation. J. Comput. Syst. Sci. 7(2): 189-198 (1973)

Mike Paterson, Larry J. Stockmeyer: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. 2(1): 60-66 (1973)

Leslie G. Valiant, Mike Paterson: Deterministic one-counter automata. Automatentheorie und Formale Sprachen 1973: 104-115

Mike Paterson: Tape Bounds for Time-Bounded Turing Machines. J. Comput. Syst. Sci. 6(2): 116-124 (1972)

Mike Paterson: Decision problems in computational models. International Sympoisum on Theoretical Programming 1972: 85-85

J. Ian Munro, Mike Paterson: Optimal Algorithms for Parallel Polynomial Evaluation. SWAT (FOCS) 1971: 132-139

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

David C. Luckham, David Michael Ritchie Park, Mike Paterson: On Formalised Computer Programs. J. Comput. Syst. Sci. 4(3): 220-249 (1970)

Mike Paterson: Tape-Bounds for Time-Bounded Turing Machines. SWAT (FOCS) 1970: 73-75