Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Mike Paterson
2010 – today
- 2011
[j67]Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson: False-Name Manipulations in Weighted Voting Games. J. Artif. Intell. Res. (JAIR) 40: 57-93 (2011)
2000 – 2009
- 2009
- [j66]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)
- [j65]
- [j64]Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick: Maximum Overhang. The American Mathematical Monthly 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
- [j63]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
- [j62]Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs. J. ACM 54(6) (2007)
- [e4]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
- 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]
- 2005
- [j61]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. Electronic Colloquium on Computational Complexity (ECCC)(121) (2005)
- 2004
- [j60]Leslie Ann Goldberg, Russell A. Martin, Mike Paterson: Random sampling of 3-colorings in Z2. Random Struct. Algorithms 24(3): 279-302 (2004)
- [j59]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)
- [j58]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]
- 2003
- [j57]Leslie Ann Goldberg, Mark Jerrum, Mike Paterson: The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2): 133-154 (2003)
- [j56]Kazuo Iwama, Akihiro Matsuura, Mike Paterson: A family of NFAs which need 2n- deterministic states. Theor. Comput. Sci. 1-3(301): 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
- [j55]Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto: Permutation Communication in All-Optical Rings. Parallel Processing Letters 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
- [j54]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)
- [j53]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)
- 2000
- [j52]Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan: Contention resolution with constant expected delay. J. ACM 47(6): 1048-1096 (2000)
- [j51]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 (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
1990 – 1999
- 1999
- [j50]Michael J. Fischer, Mike Paterson: Optimal Layout of Edge-weighted Forests. Discrete Applied Mathematics 90(1-3): 135-159 (1999)
- [j49]Mike Paterson: The chip in your wallet - The technology of security in smartcard chip manufacture. Inf. Sec. Techn. Report 4(2): 13-18 (1999)
- [j48]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 (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
- 1998
- [j47]Akira Maruoka, Mike Paterson, Hirotaka Koizumi: Consistency of Natural Relations on Sets. Combinatorics, Probability & Computing 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
- [j46]Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. Computational Complexity 6(1): 29-45 (1997)
- [j45]David Eppstein, Mike Paterson, F. Frances Yao: On Nearest-Neighbor Graphs. Discrete & Computational Geometry 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
- [j44]Mike Paterson, Teresa M. Przytycka: On the Complexity of String Folding. Discrete Applied Mathematics 71(1-3): 217-230 (1996)
- [j43]Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996)
- [j42]Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. 158(1&2): 343-359 (1996)
- [c38]
- [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]
- 1995
- [j41]Alain P. Hiltgen, Mike Paterson: PI_k Mass Production and an Optimal Circuit for the Neciporuk Slice. Computational Complexity 5(2): 132-154 (1995)
- [j40]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)
- [j39]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]
- [c34]
- [c33]
- [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. Electronic Colloquium on Computational Complexity (ECCC) 2(1) (1995)
- [i1]Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs. Electronic Colloquium on Computational Complexity (ECCC) 2(40) (1995)
- 1994
- [j38]
- [j37]Mike Paterson: David Michael Ritchie Park (1935-1990) in Memoriam. Theor. Comput. Sci. 133(1): 187-200 (1994)
- [c31]
- [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
- [j36]Mike Paterson, Uri Zwick: Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. Computational Complexity 3: 262-291 (1993)
- [j35]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)
- [j34]Mike Paterson, Uri Zwick: Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms 4(2): 135-150 (1993)
- [j33]
- [c29]
- [c28]Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Which Patterns are Hard to Find? ISTCS 1993: 59-68
- 1992
- [j32]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]
- [c25]
- [c24]Alan Gibbons, Mike Paterson: Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. SPAA 1992: 257-263
- [c23]
- 1991
- [j31]William F. McColl, Mike Paterson, B. H. Bowditch: Planar Acyclic Computation. Inf. Comput. 90(2): 178-193 (1991)
- [j30]Mike Paterson, Alexander A. Razborov: The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991)
- [c22]
- [c21]
- 1990
- [j29]
- [j28]Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. Algorithmica 5(3): 407-419 (1990)
- [j27]Mike Paterson, F. Frances Yao: Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling. Discrete & Computational Geometry 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 (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
1980 – 1989
- 1989
- [j26]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. Symposium on Computational Geometry 1989: 23-32
- 1988
- [j25]
- [c17]Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. Symposium on Computational Geometry 1988: 241-251
- 1987
- [j24]William F. McColl, Mike Paterson: The Planar Realization of Boolean Functions. Inf. Process. Lett. 24(3): 165-170 (1987)
- 1986
- [j23]Mike Paterson, Ingo Wegener: Nearly Optimal Hierarchies for Network and Formula Size. Acta Inf. 23(2): 217-221 (1986)
- [j22]
- 1985
- [j21]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
- [j20]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
- [j19]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
- [j18]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)
- [j17]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)
- 1981
- [j16]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)
- [j15]Francine Berman, Mike Paterson: Propositional Dynamic Logic is Weaker without Tests. Theor. Comput. Sci. 16: 321-328 (1981)
- [c13]Mike Paterson, Walter L. Ruzzo, Lawrence Snyder: Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract). STOC 1981: 293-299
- 1980
- [j14]William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980)
- [j13]Peter Klein, Mike Paterson: Asymtotically Optimal Circuit for a Storage Access Function. IEEE Trans. Computers 29(8): 737-738 (1980)
- [j12]J. Ian Munro, Mike Paterson: Selection and Sorting with Limited Storage. Theor. Comput. Sci. 12: 315-323 (1980)
- [c12]
1970 – 1979
- 1979
- [c11]Mike Paterson: The linear postman: a message-forwarding algorithm using sequential storage. Algorithms in Modern Mathematics and Computer Science 1979: 463
- 1978
- [j11]
- [c10]
- 1977
- [j10]William F. McColl, Mike Paterson: The Depth of All Boolean Functions. SIAM J. Comput. 6(2): 373-380 (1977)
- [c9]
- 1976
- [j9]Arnold Schönhage, Mike Paterson, Nicholas Pippenger: Finding the Median. J. Comput. Syst. Sci. 13(2): 184-199 (1976)
- [j8]Mike Paterson, Leslie G. Valiant: Circuit Size is Nonlinear in Depth. Theor. Comput. Sci. 2(3): 397-400 (1976)
- [c8]
- 1975
- [j7]Leslie G. Valiant, Mike Paterson: Deterministic One-Counter Automata. J. Comput. Syst. Sci. 10(3): 340-350 (1975)
- [j6]Mike Paterson: Complexity of Monotone Networks for Boolean Matrix Product. Theor. Comput. Sci. 1(1): 13-20 (1975)
- [c7]Michael J. Fischer, Albert R. Meyer, Mike Paterson: Lower Bounds on the Size of Boolean Formulas: Preliminary Report. STOC 1975: 37-44
- 1974
- [j5]Ronald V. Book, Maurice Nivat, Mike Paterson: Reversal-Bounded Acceptors and Intersections of Linear Languages. SIAM J. Comput. 3(4): 283-295 (1974)
- [c6]Ronald V. Book, Maurice Nivat, Mike Paterson: Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract). STOC 1974: 290-296
- 1973
- [j4]J. Ian Munro, Mike Paterson: Optimal Algorithms for Parallel Polynomial Evaluation. J. Comput. Syst. Sci. 7(2): 189-198 (1973)
- [j3]Mike Paterson, Larry J. Stockmeyer: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. 2(1): 60-66 (1973)
- [c5]Leslie G. Valiant, Mike Paterson: Deterministic one-counter automata. Automatentheorie und Formale Sprachen 1973: 104-115
- 1972
- [j2]Mike Paterson: Tape Bounds for Time-Bounded Turing Machines. J. Comput. Syst. Sci. 6(2): 116-124 (1972)
- [c4]Mike Paterson: Decision problems in computational models. International Sympoisum on Theoretical Programming 1972: 85-85
- 1971
- [c3]J. Ian Munro, Mike Paterson: Optimal Algorithms for Parallel Polynomial Evaluation. SWAT (FOCS) 1971: 132-139
- [c2]Mike Paterson, Larry J. Stockmeyer: Bounds on the Evaluation Time for Rational Polynomials. SWAT (FOCS) 1971: 140-143
- 1970
- [j1]David C. Luckham, David Michael Ritchie Park, Mike Paterson: On Formalised Computer Programs. J. Comput. Syst. Sci. 4(3): 220-249 (1970)
- [c1]
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-04-17 21:42 CEST by the dblp team