default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMike Paterson
Person information
- affiliation: University of Warwick, Coventry, UK
- award (2001): Dijkstra Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c66]Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini:
Learning a Social Network by Influencing Opinions. AAMAS 2024: 363-371- 2023
- [j71]Artur Czumaj, George Kontogeorgiou, Mike Paterson:
Haystack hunting hints and locker room communication. Random Struct. Algorithms 62(4): 832-856 (2023) - 2022
- [j70]Kazuo Iwama, Mike Paterson
:
Bounded Hanoi. Am. Math. Mon. 129(4): 303-319 (2022) - 2021
- [c65]Artur Czumaj, George Kontogeorgiou, Mike Paterson:
Haystack Hunting Hints and Locker Room Communication. ICALP 2021: 58:1-58:20 - 2020
- [c64]Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini:
Convergence of Opinion Diffusion is PSPACE-Complete. AAAI 2020: 7103-7110 - [i12]Dmitry Chistikov, Olga Goulko, Adrian Kent, Mike Paterson:
Globe-hopping. CoRR abs/2001.06442 (2020) - [i11]Artur Czumaj, George Kontogeorgiou, Mike Paterson:
Combinatorial Communication in the Locker Room. CoRR abs/2008.11448 (2020)
2010 – 2019
- 2019
- [i10]Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini:
Convergence of Opinion Diffusion is PSPACE-complete. CoRR abs/1912.09864 (2019) - 2017
- [i9]David B. A. Epstein, Mike Paterson:
Maximizing the area of intersection of rectangles. CoRR abs/1703.08658 (2017) - 2014
- [c63]Thomas Dueholm Hansen, Mike Paterson, Uri Zwick:
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. SODA 2014: 874-881 - [i8]Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson:
False-Name Manipulations in Weighted Voting Games. CoRR abs/1401.3869 (2014) - 2011
- [j69]Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson:
False-Name Manipulations in Weighted Voting Games. J. Artif. Intell. Res. 40: 57-93 (2011)
2000 – 2009
- 2009
- [j68]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) - [j67]Mike Paterson, Uri Zwick:
Overhang. Am. Math. Mon. 116(1): 19-44 (2009) - [j66]Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick:
Maximum Overhang. Am. Math. Mon. 116(9): 763-787 (2009) - [c62]Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani:
Power Indices in Spanning Connectivity Games. AAIM 2009: 55-67 - [c61]Haris Aziz, Mike Paterson:
False name manipulations in weighted voting games: splitting, merging and annexation. AAMAS (1) 2009: 409-416 - [c60]Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani:
Wiretapping a Hidden Network. WINE 2009: 438-446 - [i7]Haris Aziz, Mike Paterson:
False name manipulations in weighted voting games: splitting, merging and annexation. CoRR abs/0905.3348 (2009) - [i6]Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani:
Spanning connectivity games. CoRR abs/0906.3643 (2009) - [i5]Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani:
Wiretapping a hidden network. CoRR abs/0909.5293 (2009) - 2008
- [j65]Marcin Jurdzinski, Mike Paterson, Uri Zwick:
A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM J. Comput. 38(4): 1519-1532 (2008) - [c59]Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita:
Polynomial-Time Construction of Linear Network Coding. ICALP (1) 2008: 271-282 - [c58]Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick:
Maximum overhang. SODA 2008: 756-765 - [c57]Hiro Ito, Mike Paterson, Kenya Sugihara:
Multi-commodity Source Location Problems and Price of Greed. WALCOM 2008: 169-179 - [i4]Haris Aziz, Mike Paterson:
Computing voting power in easy weighted voting games. CoRR abs/0811.2497 (2008) - 2007
- [j64]Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. J. ACM 54(6): 27 (2007) - [e4]Bo Chen, Mike Paterson, Guochuan Zhang:
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 [contents] - 2006
- [j63]Leslie Ann Goldberg, Markus Jalsenius, Russell Martin, Mike Paterson:
Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2. LMS J. Comput. Math. 9: 1-20 (2006) - [c56]Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) 2006: 38-49 - [c55]Marcin Jurdzinski, Mike Paterson, Uri Zwick:
A deterministic subexponential algorithm for solving parity games. SODA 2006: 117-123 - [c54]Mike Paterson, Uri Zwick:
Overhang. SODA 2006: 231-240 - 2005
- [j62]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) - [i3]Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j61]Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
Random sampling of 3-colorings in Z2. Random Struct. Algorithms 24(3): 279-302 (2004) - [j60]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) - [j59]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) - [c53]Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
trong Spatial Mixing for Lattice Graphs with Fewer Colours. FOCS 2004: 562-571 - [c52]Mike Paterson:
Analysis of Scheduling Algorithms for Proportionate Fairness. LATIN 2004: 1 - 2003
- [j58]Leslie Ann Goldberg, Mark Jerrum, Mike Paterson:
The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2): 133-154 (2003) - [j57]Kazuo Iwama, Akihiro Matsuura, Mike Paterson:
A family of NFAs which need 2n- deterministic states. Theor. Comput. Sci. 301(1-3): 451-462 (2003) - [c51]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 - 2002
- [j56]Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto:
Permutation Communication in All-Optical Rings. Parallel Process. Lett. 12(1): 23-29 (2002) - [c50]Leslie Ann Goldberg, Steven Kelk, Mike Paterson:
The complexity of choosing an H-colouring (nearly) uniformly at random. STOC 2002: 53-62 - 2001
- [j55]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) - [j54]Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk:
Better Approximation Guarantees for Job-Shop Scheduling. SIAM J. Discret. Math. 14(1): 67-92 (2001) - 2000
- [j53]Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan:
Contention resolution with constant expected delay. J. ACM 47(6): 1048-1096 (2000) - [j52]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) - [c49]Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson:
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. ICALP 2000: 705-716 - [c48]Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson:
Tight Size Bounds for Packet Headers in Narrow Meshes. ICALP 2000: 756-767 - [c47]Kazuo Iwama, Akihiro Matsuura, Mike Paterson:
A Family of NFA's Which Need 2n -alpha Deterministic States. MFCS 2000: 436-445 - [c46]Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin:
Communication complexity of document exchange. SODA 2000: 197-206 - [e3]Mike Paterson:
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 [contents]
1990 – 1999
- 1999
- [j51]Michael J. Fischer, Mike Paterson:
Optimal Layout of Edge-weighted Forests. Discret. Appl. Math. 90(1-3): 135-159 (1999) - [j50]Mike Paterson:
The chip in your wallet - The technology of security in smartcard chip manufacture. Inf. Secur. Tech. Rep. 4(2): 13-18 (1999) - [j49]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) - [c45]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 - [c44]S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel:
Compact Grid Layouts of Multi-Level Networks. STOC 1999: 455-463 - [e2]Maxime Crochemore, Mike Paterson:
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 [contents] - 1998
- [j48]Akira Maruoka, Mike Paterson, Hirotaka Koizumi:
Consistency of Natural Relations on Sets. Comb. Probab. Comput. 7(3): 281-293 (1998) - [c43]Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto:
On permutation communications in all-optical rings. SIROCCO 1998: 1-9 - [c42]Sanjeev Khanna, S. Muthukrishnan, Mike Paterson:
On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393 - [c41]Shimon Even, S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp:
Layout of the Batcher Bitonic Sorter (Extended Abstract). SPAA 1998: 172-181 - 1997
- [j47]Amos Beimel, Anna Gál, Mike Paterson:
Lower Bounds for Monotone Span Programs. Comput. Complex. 6(1): 29-45 (1997) - [j46]David Eppstein, Mike Paterson, F. Frances Yao:
On Nearest-Neighbor Graphs. Discret. Comput. Geom. 17(3): 263-282 (1997) - [c40]Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson:
On Weak Circular Squares in Binary Words. CPM 1997: 76-82 - [c39]Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk:
Better Approximation Guarantees for Job-shop Scheduling. SODA 1997: 599-608 - 1996
- [j45]Mike Paterson, Teresa M. Przytycka:
On the Complexity of String Folding. Discret. Appl. Math. 71(1-3): 217-230 (1996) - [j44]Peter Bro Miltersen, Mike Paterson, Jun Tarui:
The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996) - [j43]Uri Zwick, Mike Paterson:
The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. 158(1&2): 343-359 (1996) - [c38]Mike Paterson, Teresa M. Przytycka:
On the Complexity of String Folding. ICALP 1996: 658-669 - [c37]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 - [c36]Mike Paterson:
Progress in Selection. SWAT 1996: 368-379 - 1995
- [j42]Alain P. Hiltgen, Mike Paterson:
PIk Mass Production and an Optimal Circuit for the Neciporuk Slice. Comput. Complex. 5(2): 132-154 (1995) - [j41]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) - [j40]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) - [c35]Uri Zwick, Mike Paterson:
The Complexity of Mean Payoff Games. COCOON 1995: 1-10 - [c34]Mike Paterson, Aravind Srinivasan:
Contention Resolution with Bounded Delay. FOCS 1995: 104-113 - [c33]Amos Beimel, Anna Gál, Mike Paterson:
Lower Bounds for Monotone Span Programs. FOCS 1995: 674-681 - [c32]Mike Paterson, Shlomit Tassa, Uri Zwick:
Looking for MUM and DAD: Text-Text Comparisons Do Help. FSTTCS 1995: 1-10 - [i2]Amos Beimel, Anna Gál, Mike Paterson:
Lower Bounds for Monotone Span Programs. Electron. Colloquium Comput. Complex. TR95 (1995) - [i1]Uri Zwick, Mike Paterson:
The Complexity of Mean Payoff Games on Graphs. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [j39]Michael J. Fischer, Mike Paterson:
Fishspear: A Priority Queue Algorithm. J. ACM 41(1): 3-30 (1994) - [j38]Mike Paterson:
David Michael Ritchie Park (1935-1990) in Memoriam. Theor. Comput. Sci. 133(1): 187-200 (1994) - [c31]Mike Paterson, Vlado Dancík:
Longest Common Subsequences. MFCS 1994: 127-142 - [c30]Vlado Dancík, Mike Paterson:
Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. STACS 1994: 669-678 - 1993
- [j37]Mike Paterson, Uri Zwick:
Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. Comput. Complex. 3: 262-291 (1993) - [j36]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) - [j35]Mike Paterson, Uri Zwick:
Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms 4(2): 135-150 (1993) - [j34]Uri Zwick, Mike Paterson:
The Memory Game. Theor. Comput. Sci. 110(1): 169-196 (1993) - [c29]Mike Paterson:
Evolution of an Algorithm. ESA 1993: 306-308 - [c28]Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick:
Which Patterns are Hard to Find? ISTCS 1993: 59-68 - 1992
- [j33]Mike Paterson, F. Frances Yao:
Optimal Binary Space Partitions for Orthogonal Objects. J. Algorithms 13(1): 99-113 (1992) - [c27]Peter Bro Miltersen, Mike Paterson, Jun Tarui:
The Asymptotic Complexity of Merging Networks. FOCS 1992: 236-246 - [c26]Mike Paterson, F. Frances Yao:
On Nearest-Neighbor Graphs. ICALP 1992: 416-426 - [c25]Mike Paterson:
Boolean Circuit Complexity. ISAAC 1992: 187 - [c24]Alan Gibbons, Mike Paterson:
Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. SPAA 1992: 257-263 - [c23]Mike Paterson, Uri Zwick:
Shallow Multiplication Circuits and Wise Financial Investments. STOC 1992: 429-437 - 1991
- [j32]William F. McColl, Mike Paterson, Brian H. Bowditch:
Planar Acyclic Computation. Inf. Comput. 90(2): 178-193 (1991) - [j31]Mike Paterson, Alexander A. Razborov:
The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991) - [c22]Mike Paterson, Uri Zwick:
Shrinkage of de~Morgan formulae under restriction. FOCS 1991: 324-333 - [c21]Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán:
The MINSUMCUT Problem. WADS 1991: 65-89 - 1990
- [j30]Mike Paterson:
Improved Sorting Networks with O(log N) Depth. Algorithmica 5(1): 65-92 (1990) - [j29]Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao:
Computing Euclidean Maximum Spanning Trees. Algorithmica 5(3): 407-419 (1990) - [j28]Mike Paterson, F. Frances Yao:
Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling. Discret. Comput. Geom. 5: 485-503 (1990) - [c20]Mike Paterson, Nicholas Pippenger, Uri Zwick:
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions. FOCS 1990: 642-650 - [c19]Mike Paterson, F. Frances Yao:
Optimal Binary Space Partitions for Orthogonal Objects. SODA 1990: 100-106 - [e1]Mike Paterson:
Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings. Lecture Notes in Computer Science 443, Springer 1990, ISBN 3-540-52826-1 [contents]
1980 – 1989
- 1989
- [j27]F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, Mike Paterson:
Partitioning Space for Range Queries. SIAM J. Comput. 18(2): 371-384 (1989) - [c18]Mike Paterson, F. Frances Yao:
Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling. SCG 1989: 23-32 - 1988
- [j26]Mike Paterson:
Universal Chains and Wiring Layouts. SIAM J. Discret. Math. 1(1): 80-85 (1988) - [c17]Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao:
Computing Euclidean Maximum Spanning Trees. SCG 1988: 241-251 - 1987
- [j25]William F. McColl, Mike Paterson:
The Planar Realization of Boolean Functions. Inf. Process. Lett. 24(3): 165-170 (1987) - 1986
- [j24]Mike Paterson, Ingo Wegener:
Nearly Optimal Hierarchies for Network and Formula Size. Acta Informatica 23(2): 217-221 (1986) - [j23]Mike Paterson, F. Frances Yao:
Point Retrieval for Polygons. J. Algorithms 7(3): 441-447 (1986) - 1985
- [j22]Michael J. Fischer, Nancy A. Lynch, Mike Paterson:
Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32(2): 374-382 (1985) - [c16]Michael J. Fischer, Mike Paterson:
Dynamic Monotone Priorities on Planar Sets (Extended Abstract). FOCS 1985: 289-292 - 1984
- [j21]David Harel, Mike Paterson:
Undecidability of PDL with L={a^(2i)|i>=0}. J. Comput. Syst. Sci. 29(3): 359-365 (1984) - [c15]Michael J. Fischer, Mike Paterson:
Fishspear: A Priority Queue Algorithm (Extended Abstract). FOCS 1984: 375-386 - 1983
- [j20]Michael J. Fischer, Mike Paterson:
Storage Requirements for Fair Scheduling. Inf. Process. Lett. 17(5): 249-250 (1983) - [c14]Michael J. Fischer, Nancy A. Lynch, Mike Paterson:
Impossibility of Distributed Consensus with One Faulty Process. PODS 1983: 1-7 - 1982
- [j19]Albert G. Greenberg,