2008 | ||
---|---|---|
129 | EE | Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita: Polynomial-Time Construction of Linear Network Coding. ICALP (1) 2008: 271-282 |
128 | EE | Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick: Maximum overhang. SODA 2008: 756-765 |
127 | EE | Hiro Ito, Mike Paterson, Kenya Sugihara: Multi-commodity Source Location Problems and Price of Greed. WALCOM 2008: 169-179 |
126 | EE | Haris Aziz, Mike Paterson: Computing voting power in easy weighted voting games CoRR abs/0811.2497: (2008) |
125 | EE | Marcin Jurdzinski, Mike Paterson, Uri Zwick: A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM J. Comput. 38(4): 1519-1532 (2008) |
2007 | ||
124 | 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 Springer 2007 | |
123 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs. J. ACM 54(6): (2007) |
2006 | ||
122 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) 2006: 38-49 |
121 | EE | Marcin Jurdzinski, Mike Paterson, Uri Zwick: A deterministic subexponential algorithm for solving parity games. SODA 2006: 117-123 |
120 | EE | Mike Paterson, Uri Zwick: Overhang. SODA 2006: 231-240 |
2005 | ||
119 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs Electronic Colloquium on Computational Complexity (ECCC)(121): (2005) |
118 | EE | 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) |
2004 | ||
117 | EE | Leslie Ann Goldberg, Russell A. Martin, Mike Paterson: trong Spatial Mixing for Lattice Graphs with Fewer Colours. FOCS 2004: 562-571 |
116 | EE | Mike Paterson: Analysis of Scheduling Algorithms for Proportionate Fairness. LATIN 2004: 1 |
115 | EE | Leslie Ann Goldberg, Russell A. Martin, Mike Paterson: Random sampling of 3-colorings in Z2. Random Struct. Algorithms 24(3): 279-302 (2004) |
114 | EE | 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) |
113 | EE | 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) |
2003 | ||
112 | EE | 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 |
111 | EE | Leslie Ann Goldberg, Mark Jerrum, Mike Paterson: The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2): 133-154 (2003) |
110 | EE | Kazuo Iwama, Akihiro Matsuura, Mike Paterson: A family of NFAs which need 2n- deterministic states. Theor. Comput. Sci. 1-3(301): 451-462 (2003) |
2002 | ||
109 | EE | Leslie Ann Goldberg, Steven Kelk, Mike Paterson: The complexity of choosing an H-colouring (nearly) uniformly at random. STOC 2002: 53-62 |
108 | EE | Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto: Permutation Communication in All-Optical Rings. Parallel Processing Letters 12(1): 23-29 (2002) |
2001 | ||
107 | EE | 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) |
106 | EE | 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 | ||
105 | Mike Paterson: Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings Springer 2000 | |
104 | EE | Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson: A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. ICALP 2000: 705-716 |
103 | EE | Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson: Tight Size Bounds for Packet Headers in Narrow Meshes. ICALP 2000: 756-767 |
102 | EE | Kazuo Iwama, Akihiro Matsuura, Mike Paterson: A Family of NFA's Which Need 2n -alpha Deterministic States. MFCS 2000: 436-445 |
101 | EE | Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin: Communication complexity of document exchange. SODA 2000: 197-206 |
100 | EE | Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan: Contention resolution with constant expected delay. J. ACM 47(6): 1048-1096 (2000) |
99 | EE | 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) |
1999 | ||
98 | Maxime Crochemore, Mike Paterson: Combinatorial Pattern Matching, 10th Annual Symposium, CPM 99, Warwick University, UK, July 22-24, 1999, Proceedings Springer 1999 | |
97 | EE | 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 |
96 | EE | S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel: Compact Grid Layouts of Multi-Level Networks. STOC 1999: 455-463 |
95 | EE | Michael J. Fischer, Mike Paterson: Optimal Layout of Edge-weighted Forests. Discrete Applied Mathematics 90(1-3): 135-159 (1999) |
94 | 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) | |
1998 | ||
93 | Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto: On permutation communications in all-optical rings. SIROCCO 1998: 1-9 | |
92 | Sanjeev Khanna, S. Muthukrishnan, Mike Paterson: On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393 | |
91 | EE | Shimon Even, S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp: Layout of the Batcher Bitonic Sorter (Extended Abstract). SPAA 1998: 172-181 |
90 | Akira Maruoka, Mike Paterson, Hirotaka Koizumi: Consistency of Natural Relations on Sets. Combinatorics, Probability & Computing 7(3): 281-293 (1998) | |
1997 | ||
89 | Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson: On Weak Circular Squares in Binary Words. CPM 1997: 76-82 | |
88 | Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk: Better Approximation Guarantees for Job-shop Scheduling. SODA 1997: 599-608 | |
87 | Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. Computational Complexity 6(1): 29-45 (1997) | |
86 | EE | David Eppstein, Mike Paterson, F. Frances Yao: On Nearest-Neighbor Graphs. Discrete & Computational Geometry 17(3): 263-282 (1997) |
1996 | ||
85 | Mike Paterson, Teresa M. Przytycka: On the Complexity of String Folding. ICALP 1996: 658-669 | |
84 | 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 | |
83 | Mike Paterson: Progress in Selection. SWAT 1996: 368-379 | |
82 | EE | Mike Paterson, Teresa M. Przytycka: On the Complexity of String Folding. Discrete Applied Mathematics 71(1-3): 217-230 (1996) |
81 | EE | Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996) |
80 | EE | Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. 158(1&2): 343-359 (1996) |
1995 | ||
79 | Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games. COCOON 1995: 1-10 | |
78 | Mike Paterson, Aravind Srinivasan: Contention Resolution with Bounded Delay. FOCS 1995: 104-113 | |
77 | Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs. FOCS 1995: 674-681 | |
76 | Mike Paterson, Shlomit Tassa, Uri Zwick: Looking for MUM and DAD: Text-Text Comparisons Do Help. FSTTCS 1995: 1-10 | |
75 | Alain P. Hiltgen, Mike Paterson: PI_k Mass Production and an Optimal Circuit for the Neciporuk Slice. Computational Complexity 5(2): 132-154 (1995) | |
74 | EE | Amos Beimel, Anna Gál, Mike Paterson: Lower Bounds for Monotone Span Programs Electronic Colloquium on Computational Complexity (ECCC) 2(1): (1995) |
73 | EE | Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games on Graphs Electronic Colloquium on Computational Complexity (ECCC) 2(40): (1995) |
72 | 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) | |
71 | 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) | |
1994 | ||
70 | Mike Paterson, Vlado Dancík: Longest Common Subsequences. MFCS 1994: 127-142 | |
69 | Vlado Dancík, Mike Paterson: Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. STACS 1994: 669-678 | |
68 | EE | Michael J. Fischer, Mike Paterson: Fishspear: A Priority Queue Algorithm. J. ACM 41(1): 3-30 (1994) |
67 | Mike Paterson: David Michael Ritchie Park (1935-1990) in Memoriam. Theor. Comput. Sci. 133(1): 187-200 (1994) | |
1993 | ||
66 | Mike Paterson: Evolution of an Algorithm. ESA 1993: 306-308 | |
65 | Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick: Which Patterns are Hard to Find? ISTCS 1993: 59-68 | |
64 | Mike Paterson, Uri Zwick: Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. Computational Complexity 3: 262-291 (1993) | |
63 | 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) | |
62 | Mike Paterson, Uri Zwick: Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms 4(2): 135-150 (1993) | |
61 | Uri Zwick, Mike Paterson: The Memory Game. Theor. Comput. Sci. 110(1): 169-196 (1993) | |
1992 | ||
60 | Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks FOCS 1992: 236-246 | |
59 | Mike Paterson, F. Frances Yao: On Nearest-Neighbor Graphs. ICALP 1992: 416-426 | |
58 | Mike Paterson: Boolean Circuit Complexity. ISAAC 1992: 187 | |
57 | EE | Alan Gibbons, Mike Paterson: Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. SPAA 1992: 257-263 |
56 | Mike Paterson, Uri Zwick: Shallow Multiplication Circuits and Wise Financial Investments STOC 1992: 429-437 | |
55 | Mike Paterson, F. Frances Yao: Optimal Binary Space Partitions for Orthogonal Objects. J. Algorithms 13(1): 99-113 (1992) | |
1991 | ||
54 | Mike Paterson, Uri Zwick: Shrinkage of de~Morgan formulae under restriction FOCS 1991: 324-333 | |
53 | Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán: The MINSUMCUT Problem. WADS 1991: 65-89 | |
52 | William F. McColl, Mike Paterson, B. H. Bowditch: Planar Acyclic Computation Inf. Comput. 90(2): 178-193 (1991) | |
51 | Mike Paterson, Alexander A. Razborov: The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991) | |
1990 | ||
50 | Mike Paterson: Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, July 16-20, 1990, Proceedings Springer 1990 | |
49 | Mike Paterson, Nicholas Pippenger, Uri Zwick: Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions FOCS 1990: 642-650 | |
48 | Mike Paterson, F. Frances Yao: Optimal Binary Space Partitions for Orthogonal Objects. SODA 1990: 100-106 | |
47 | Mike Paterson: Improved Sorting Networks with O(log N) Depth. Algorithmica 5(1): 65-92 (1990) | |
46 | Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. Algorithmica 5(3): 407-419 (1990) | |
45 | Mike Paterson, F. Frances Yao: Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling. Discrete & Computational Geometry 5: 485-503 (1990) | |
1989 | ||
44 | EE | Mike Paterson, F. Frances Yao: Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling. Symposium on Computational Geometry 1989: 23-32 |
43 | F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, Mike Paterson: Partitioning Space for Range Queries. SIAM J. Comput. 18(2): 371-384 (1989) | |
1988 | ||
42 | EE | Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao: Computing Euclidean Maximum Spanning Trees. Symposium on Computational Geometry 1988: 241-251 |
41 | Mike Paterson: Universal Chains and Wiring Layouts. SIAM J. Discrete Math. 1(1): 80-85 (1988) | |
1987 | ||
40 | William F. McColl, Mike Paterson: The Planar Realization of Boolean Functions. Inf. Process. Lett. 24(3): 165-170 (1987) | |
1986 | ||
39 | Mike Paterson, Ingo Wegener: Nearly Optimal Hierarchies for Network and Formula Size. Acta Inf. 23(2): 217-221 (1986) | |
38 | Mike Paterson, F. Frances Yao: Point Retrieval for Polygons. J. Algorithms 7(3): 441-447 (1986) | |
1985 | ||
37 | Michael J. Fischer, Mike Paterson: Dynamic Monotone Priorities on Planar Sets (Extended Abstract) FOCS 1985: 289-292 | |
36 | EE | Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process J. ACM 32(2): 374-382 (1985) |
1984 | ||
35 | Michael J. Fischer, Mike Paterson: Fishspear: A Priority Queue Algorithm (Extended Abstract) FOCS 1984: 375-386 | |
34 | David Harel, Mike Paterson: Undecidability of PDL with L={a^(2i)|i>=0}. J. Comput. Syst. Sci. 29(3): 359-365 (1984) | |
1983 | ||
33 | EE | Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. PODS 1983: 1-7 |
32 | Michael J. Fischer, Mike Paterson: Storage Requirements for Fair Scheduling. Inf. Process. Lett. 17(5): 249-250 (1983) | |
1982 | ||
31 | 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) | |
30 | 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 | ||
29 | Mike Paterson, Walter L. Ruzzo, Lawrence Snyder: Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) STOC 1981: 293-299 | |
28 | 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) | |
27 | Francine Berman, Mike Paterson: Propositional Dynamic Logic is Weaker without Tests. Theor. Comput. Sci. 16: 321-328 (1981) | |
1980 | ||
26 | Michael J. Fischer, Mike Paterson: Optimal Tree Layout (Preliminary Version) STOC 1980: 177-189 | |
25 | Peter Klein, Mike Paterson: Asymtotically Optimal Circuit for a Storage Access Function. IEEE Trans. Computers 29(8): 737-738 (1980) | |
24 | William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980) | |
23 | J. Ian Munro, Mike Paterson: Selection and Sorting with Limited Storage. Theor. Comput. Sci. 12: 315-323 (1980) | |
1979 | ||
22 | Mike Paterson: The linear postman: a message-forwarding algorithm using sequential storage. Algorithms in Modern Mathematics and Computer Science 1979: 463 | |
1978 | ||
21 | J. Ian Munro, Mike Paterson: Selection and Sorting with Limited Storage FOCS 1978: 253-258 | |
20 | Mike Paterson, Mark N. Wegman: Linear Unification. J. Comput. Syst. Sci. 16(2): 158-167 (1978) | |
1977 | ||
19 | Mike Paterson: New bounds on formula size. Theoretical Computer Science 1977: 17-26 | |
18 | William F. McColl, Mike Paterson: The Depth of All Boolean Functions. SIAM J. Comput. 6(2): 373-380 (1977) | |
1976 | ||
17 | Mike Paterson, Mark N. Wegman: Linear Unification STOC 1976: 181-186 | |
16 | Arnold Schönhage, Mike Paterson, Nicholas Pippenger: Finding the Median. J. Comput. Syst. Sci. 13(2): 184-199 (1976) | |
15 | Mike Paterson, Leslie G. Valiant: Circuit Size is Nonlinear in Depth. Theor. Comput. Sci. 2(3): 397-400 (1976) | |
1975 | ||
14 | Michael J. Fischer, Albert R. Meyer, Mike Paterson: Lower Bounds on the Size of Boolean Formulas: Preliminary Report STOC 1975: 37-44 | |
13 | Leslie G. Valiant, Mike Paterson: Deterministic One-Counter Automata. J. Comput. Syst. Sci. 10(3): 340-350 (1975) | |
12 | Mike Paterson: Complexity of Monotone Networks for Boolean Matrix Product. Theor. Comput. Sci. 1(1): 13-20 (1975) | |
1974 | ||
11 | Ronald V. Book, Maurice Nivat, Mike Paterson: Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract) STOC 1974: 290-296 | |
10 | Ronald V. Book, Maurice Nivat, Mike Paterson: Reversal-Bounded Acceptors and Intersections of Linear Languages. SIAM J. Comput. 3(4): 283-295 (1974) | |
1973 | ||
9 | Leslie G. Valiant, Mike Paterson: Deterministic one-counter automata. Automatentheorie und Formale Sprachen 1973: 104-115 | |
8 | J. Ian Munro, Mike Paterson: Optimal Algorithms for Parallel Polynomial Evaluation. J. Comput. Syst. Sci. 7(2): 189-198 (1973) | |
7 | Mike Paterson, Larry J. Stockmeyer: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. 2(1): 60-66 (1973) | |
1972 | ||
6 | Mike Paterson: Decision problems in compputation models. International Sympoisum on Theoretical Programming 1972: 85-85 | |
5 | Mike Paterson: Tape Bounds for Time-Bounded Turing Machines. J. Comput. Syst. Sci. 6(2): 116-124 (1972) | |
1971 | ||
4 | J. Ian Munro, Mike Paterson: Optimal Algorithms for Parallel Polynomial Evaluation FOCS 1971: 132-139 | |
3 | Mike Paterson, Larry J. Stockmeyer: Bounds on the Evaluation Time for Rational Polynomials FOCS 1971: 140-143 | |
1970 | ||
2 | Mike Paterson: Tape-Bounds for Time-Bounded Turing Machines FOCS 1970: 73-75 | |
1 | David C. Luckham, David Michael Ritchie Park, Mike Paterson: On Formalised Computer Programs. J. Comput. Syst. Sci. 4(3): 220-249 (1970) |