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, Richard E. Ladner, Mike Paterson, Zvi Galil:
Efficient Parallel Algorithms for Linear Recurrence Computation. Inf. Process. Lett. 15(1): 31-35 (1982) - [j18]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
- [j17]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) - [j16]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
- [j15]William J. Masek, Mike Paterson:
A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20(1): 18-31 (1980) - [j14]Peter Klein, Mike Paterson:
Asymtotically Optimal Circuit for a Storage Access Function. IEEE Trans. Computers 29(8): 737-738 (1980) - [j13]J. Ian Munro, Mike Paterson:
Selection and Sorting with Limited Storage. Theor. Comput. Sci. 12: 315-323 (1980) - [c12]Michael J. Fischer, Mike Paterson:
Optimal Tree Layout (Preliminary Version). STOC 1980: 177-189
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
- [j12]Mike Paterson, Mark N. Wegman:
Linear Unification. J. Comput. Syst. Sci. 16(2): 158-167 (1978) - [c10]J. Ian Munro, Mike Paterson:
Selection and Sorting with Limited Storage. FOCS 1978: 253-258 - 1977
- [j11]William F. McColl, Mike Paterson:
The Depth of All Boolean Functions. SIAM J. Comput. 6(2): 373-380 (1977) - [c9]Mike Paterson:
New bounds on formula size. Theoretical Computer Science 1977: 17-26 - 1976
- [j10]Arnold Schönhage, Mike Paterson, Nicholas Pippenger:
Finding the Median. J. Comput. Syst. Sci. 13(2): 184-199 (1976) - [j9]Mike Paterson, Leslie G. Valiant:
Circuit Size is Nonlinear in Depth. Theor. Comput. Sci. 2(3): 397-400 (1976) - [c8]Mike Paterson, Mark N. Wegman:
Linear Unification. STOC 1976: 181-186 - 1975
- [j8]Leslie G. Valiant, Mike Paterson:
Deterministic One-Counter Automata. J. Comput. Syst. Sci. 10(3): 340-350 (1975) - [j7]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
- [j6]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
- [j5]J. Ian Munro, Mike Paterson:
Optimal Algorithms for Parallel Polynomial Evaluation. J. Comput. Syst. Sci. 7(2): 189-198 (1973) - [j4]Mike Paterson, Larry J. Stockmeyer:
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. 2(1): 60-66 (1973) - [j3]M. Bauer, D. Brand, Michael J. Fischer, Albert R. Meyer, Mike Paterson:
A note on disjunctive form tautologies. SIGACT News 5(2): 17-20 (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 1971: 132-139 - [c2]Mike Paterson, Larry J. Stockmeyer:
Bounds on the Evaluation Time for Rational Polynomials. SWAT 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]Mike Paterson:
Tape-Bounds for Time-Bounded Turing Machines. SWAT 1970: 73-75
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:13 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
