Mike Paterson

ORCID

Publication Activity (10 Years)

Years Active: 1970-2024
Publications (10 Years): 9

Top Venues

Publications

Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini
Learning a Social Network by Influencing Opinions. AAMAS (2024)
Artur Czumaj, George Kontogeorgiou, Mike Paterson
Haystack hunting hints and locker room communication. Random Struct. Algorithms 62 (4) (2023)
Kazuo Iwama, Mike Paterson
Bounded Hanoi. Am. Math. Mon. 129 (4) (2022)
Artur Czumaj, George Kontogeorgiou, Mike Paterson
Haystack Hunting Hints and Locker Room Communication. ICALP (2021)
Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini
Convergence of Opinion Diffusion is PSPACE-Complete. AAAI (2020)
Dmitry Chistikov, Olga Goulko, Adrian Kent, Mike Paterson
Globe-hopping. CoRR (2020)
Artur Czumaj, George Kontogeorgiou, Mike Paterson
Combinatorial Communication in the Locker Room. CoRR (2020)
Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini
Convergence of Opinion Diffusion is PSPACE-complete. CoRR (2019)
David B. A. Epstein, Mike Paterson
Maximizing the area of intersection of rectangles. CoRR (2017)
Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson
False-Name Manipulations in Weighted Voting Games. CoRR (2014)
Thomas Dueholm Hansen, Mike Paterson, Uri Zwick
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. SODA (2014)
Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson
False-Name Manipulations in Weighted Voting Games. J. Artif. Intell. Res. 40 (2011)
Haris Aziz, Mike Paterson
False name manipulations in weighted voting games: splitting, merging and annexation CoRR (2009)
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
Maximum Overhang. Am. Math. Mon. 116 (9) (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Power Indices in Spanning Connectivity Games. AAIM (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Wiretapping a hidden network CoRR (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Wiretapping a Hidden Network. WINE (2009)
Hiro Ito, Mike Paterson, Kenya Sugihara
The Multi-Commodity Source Location Problems and the Price of Greed. J. Graph Algorithms Appl. 13 (1) (2009)
Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
Spanning connectivity games CoRR (2009)
Mike Paterson, Uri Zwick
Overhang. Am. Math. Mon. 116 (1) (2009)
Haris Aziz, Mike Paterson
False name manipulations in weighted voting games: splitting, merging and annexation. AAMAS (1) (2009)
Marcin Jurdzinski, Mike Paterson, Uri Zwick
A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM J. Comput. 38 (4) (2008)
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
Maximum overhang. SODA (2008)
Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita
Polynomial-Time Construction of Linear Network Coding. ICALP (1) (2008)
Hiro Ito, Mike Paterson, Kenya Sugihara
Multi-commodity Source Location Problems and Price of Greed. WALCOM (2008)
Haris Aziz, Mike Paterson
Computing voting power in easy weighted voting games CoRR (2008)
Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson
On counting homomorphisms to directed acyclic graphs. J. ACM 54 (6) (2007)
Mike Paterson, Uri Zwick
Overhang. SODA (2006)
Leslie Ann Goldberg, Markus Jalsenius, Russell Martin, Mike Paterson
. LMS J. Comput. Math. 9 (2006)
Marcin Jurdzinski, Mike Paterson, Uri Zwick
A deterministic subexponential algorithm for solving parity games. SODA (2006)
Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson
On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) (2006)
Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson
On counting homomorphisms to directed acyclic graphs Electron. Colloquium Comput. Complex. (121) (2005)
Leslie Ann Goldberg, Russell A. Martin, Mike Paterson
Strong Spatial Mixing with Fewer Colors for Lattice Graphs. SIAM J. Comput. 35 (2) (2005)
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) (2004)
Leslie Ann Goldberg, Steven Kelk, Mike Paterson
The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random. SIAM J. Comput. 33 (2) (2004)
Leslie Ann Goldberg, Russell A. Martin, Mike Paterson
. Random Struct. Algorithms 24 (3) (2004)
Leslie Ann Goldberg, Russell A. Martin, Mike Paterson
trong Spatial Mixing for Lattice Graphs with Fewer Colours. FOCS (2004)
Mike Paterson
Analysis of Scheduling Algorithms for Proportionate Fairness. LATIN (2004)
Leslie Ann Goldberg, Mark Jerrum, Mike Paterson
The computational complexity of two-state spin systems. Random Struct. Algorithms 23 (2) (2003)
Kazuo Iwama, Akihiro Matsuura, Mike Paterson
A family of NFAs which need 2n- deterministic states. Theor. Comput. Sci. 301 (1-3) (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)
Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto
Permutation Communication in All-Optical Rings. Parallel Process. Lett. 12 (1) (2002)
Leslie Ann Goldberg, Steven Kelk, Mike Paterson
The complexity of choosing an H-colouring (nearly) uniformly at random. STOC (2002)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Better Approximation Guarantees for Job-Shop Scheduling. SIAM J. Discret. Math. 14 (1) (2001)
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) (2001)
Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan
Contention resolution with constant expected delay. J. ACM 47 (6) (2000)
Somasundaram Ravindran, Alan Gibbons, Mike Paterson
Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theor. Comput. Sci. 249 (2) (2000)
Kazuo Iwama, Akihiro Matsuura, Mike Paterson
Deterministic States. MFCS (2000)
Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin
Communication complexity of document exchange. SODA (2000)
Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson
Tight Size Bounds for Packet Headers in Narrow Meshes. ICALP (2000)
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. ICALP (2000)
S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel
Compact Grid Layouts of Multi-Level Networks. STOC (1999)
Mike Paterson
The chip in your wallet - The technology of security in smartcard chip manufacture. Inf. Secur. Tech. Rep. 4 (2) (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)
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) (1999)
Michael J. Fischer, Mike Paterson
Optimal Layout of Edge-weighted Forests. Discret. Appl. Math. 90 (1-3) (1999)
Shimon Even, S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp
Layout of the Batcher Bitonic Sorter (Extended Abstract). SPAA (1998)
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
On Approximating Rectangle Tiling and Packing. SODA (1998)
Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto
On permutation communications in all-optical rings. SIROCCO (1998)
Akira Maruoka, Mike Paterson, Hirotaka Koizumi
Consistency of Natural Relations on Sets. Comb. Probab. Comput. 7 (3) (1998)
Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson
On Weak Circular Squares in Binary Words. CPM (1997)
David Eppstein, Mike Paterson, F. Frances Yao
On Nearest-Neighbor Graphs. Discret. Comput. Geom. 17 (3) (1997)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Better Approximation Guarantees for Job-shop Scheduling. SODA (1997)
Amos Beimel, Anna Gál, Mike Paterson
Lower Bounds for Monotone Span Programs. Comput. Complex. 6 (1) (1997)
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)
Mike Paterson, Teresa M. Przytycka
On the Complexity of String Folding. Discret. Appl. Math. 71 (1-3) (1996)
Mike Paterson, Teresa M. Przytycka
On the Complexity of String Folding. ICALP (1996)
Uri Zwick, Mike Paterson
The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. 158 (1&2) (1996)
Mike Paterson
Progress in Selection. SWAT (1996)
Peter Bro Miltersen, Mike Paterson, Jun Tarui
The Asymptotic Complexity of Merging Networks. J. ACM 43 (1) (1996)
Amos Beimel, Anna Gál, Mike Paterson
Lower Bounds for Monotone Span Programs. FOCS (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) (1995)
Uri Zwick, Mike Paterson
The Complexity of Mean Payoff Games. COCOON (1995)
Mike Paterson, Aravind Srinivasan
Contention Resolution with Bounded Delay. FOCS (1995)
Amos Beimel, Anna Gál, Mike Paterson
Lower Bounds for Monotone Span Programs Electron. Colloquium Comput. Complex. 2 (1) (1995)
Alain P. Hiltgen, Mike Paterson
Mass Production and an Optimal Circuit for the Neciporuk Slice. Comput. Complex. 5 (2) (1995)
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
Tighter Lower Bounds on the Exact Complexity of String Matching. SIAM J. Comput. 24 (1) (1995)
Mike Paterson, Shlomit Tassa, Uri Zwick
Looking for MUM and DAD: Text-Text Comparisons Do Help. FSTTCS (1995)
Uri Zwick, Mike Paterson
The Complexity of Mean Payoff Games on Graphs Electron. Colloquium Comput. Complex. 2 (40) (1995)
Michael J. Fischer, Mike Paterson
Fishspear: A Priority Queue Algorithm. J. ACM 41 (1) (1994)
Vlado Dancík, Mike Paterson
Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. STACS (1994)
Mike Paterson
David Michael Ritchie Park (1935-1990) in Memoriam. Theor. Comput. Sci. 133 (1) (1994)
Mike Paterson, Vlado Dancík
Longest Common Subsequences. MFCS (1994)
Mike Paterson, Uri Zwick
Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. Comput. Complex. 3 (1993)
Mike Paterson
Evolution of an Algorithm. ESA (1993)
Uri Zwick, Mike Paterson
The Memory Game. Theor. Comput. Sci. 110 (1) (1993)
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
Which Patterns are Hard to Find? ISTCS (1993)
Mike Paterson, Uri Zwick
Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms 4 (2) (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) (1993)
Mike Paterson, Uri Zwick
Shallow Multiplication Circuits and Wise Financial Investments STOC (1992)
Alan Gibbons, Mike Paterson
Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. SPAA (1992)
Mike Paterson, F. Frances Yao
Optimal Binary Space Partitions for Orthogonal Objects. J. Algorithms 13 (1) (1992)
Peter Bro Miltersen, Mike Paterson, Jun Tarui
The Asymptotic Complexity of Merging Networks FOCS (1992)
Mike Paterson, F. Frances Yao
On Nearest-Neighbor Graphs. ICALP (1992)
Mike Paterson
Boolean Circuit Complexity. ISAAC (1992)
William F. McColl, Mike Paterson, Brian H. Bowditch
Planar Acyclic Computation Inf. Comput. 90 (2) (1991)
Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán
The MINSUMCUT Problem. WADS (1991)
Mike Paterson, Alexander A. Razborov
The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12 (3) (1991)
Mike Paterson, Uri Zwick
Shrinkage of de~Morgan formulae under restriction FOCS (1991)
Mike Paterson, F. Frances Yao
Optimal Binary Space Partitions for Orthogonal Objects. SODA (1990)

Mike Paterson.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mike Paterson