Mike Paterson

Q: What Schools Are Affiliated With Mike Paterson

Mike Paterson is affiliated with the following schools: University of Warwick, Imperial College London, University of Oxford, Massachusetts Institute of Technology, University of Cambridge

Mike Paterson's AcademicInfluence.com Rankings

Mike Paterson

Computer Science

#356

World Rank

#371

Historical Rank

Artificial Intelligence

#263

World Rank

#268

Historical Rank

Database

#616

World Rank

#646

Historical Rank

Machine Learning

#732

World Rank

#742

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Mike Paterson Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Michael Stewart Paterson, is a British computer scientist, who was the director of the Centre for Discrete Mathematics and its Applications at the University of Warwick until 2007, and chair of the department of computer science in 2005.

(See a Problem?)

Mike Paterson's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Impossibility of distributed consensus with one faulty process (1983) (2977)
Impossibility of distributed consensus with one faulty process (1985) (2387)
A Faster Algorithm Computing String Edit Distances (1980) (704)
Optimal Packing and Covering in the Plane are NP-Complete (1981) (684)
The Complexity of Mean Payoff Games on Graphs (1996) (510)
Linear unification (1976) (499)
Selection and sorting with limited storage (1978) (493)
STRING-MATCHING AND OTHER PRODUCTS (1974) (462)
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials (1973) (276)
A deterministic subexponential algorithm for solving parity games (2006) (247)
Efficient binary space partitions for hidden-surface removal and solid modeling (1990) (229)
On Formalised Computer Programs (1970) (207)
Finding the Median (1976) (207)
On Nearest-Neighbor Graphs (1992) (206)
On the approximability of numerical taxonomy (fitting distances by tree metrics) (1996) (181)
Longest Common Subsequences (1994) (165)
Communication complexity of document exchange (1999) (152)
Deterministic One-Counter Automata (1973) (138)
Unsolvability in 3 × 3 Matrices (1970) (127)
Optimal binary space partitions for orthogonal objects (1990) (113)
On approximating rectangle tiling and packing (1998) (110)
Optimal Algorithms for Parallel Polynomial Evaluation (1971) (94)
Improved sorting networks withO(logN) depth (1990) (93)
Lower bounds for monotone span programs (1994) (88)
Bounds on minimax edge length for complete binary trees (1981) (81)
On counting homomorphisms to directed acyclic graphs (2006) (77)
Better approximation guarantees for job-shop scheduling (1997) (73)
Shrinkage of de Morgan formulae under restriction (1991) (70)
Equivalence Problems in a Model of Computation (1967) (68)
The computational complexity of two‐state spin systems (2003) (68)
Contention resolution with constant expected delay (2000) (67)
The Set of Minimal Braids is co-NP-Complete (1991) (61)
Binary partitions with applications to hidden surface removal and solid modelling (1989) (61)
Complexity of Monotone Networks for Boolean Matrix Product (1974) (58)
Strong Spatial Mixing with Fewer Colors for Lattice Graphs (2005) (56)
False-Name Manipulations in Weighted Voting Games (2014) (56)
Progress in Selection (1996) (53)
On the Complexity of String Folding (1996) (52)
Efficient Algorithm for Designing Weighted Voting Games (2007) (52)
The Complexity of Mean Payoff Games (1995) (51)
Boolean Function Complexity (1992) (51)
Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences (1994) (50)
Tape Bounds for Time-Bounded Turing Machines (1970) (47)
Power Indices in Spanning Connectivity Games (2009) (44)
Reversal-Bounded Acceptors and Intersections of Linear Languages (1974) (42)
Computing euclidean maximum spanning trees (1988) (41)
Partitioning Space for Range Queries (1989) (41)
AN IMPROVED OVERLAP ARGUMENT FOR ON-LINE MULTIPLICATION (1974) (40)
A bound on the capacity of backoff and acknowledgment-based protocols (2004) (39)
Algorithms - ESA 2000 (2003) (36)
Optimal carry save networks (1992) (36)
Efficient Parallel Algorithms for Linear Recurrence Computation (1982) (35)
False name manipulations in weighted voting games: splitting, merging and annexation (2009) (33)
Omega(n log n) Lower Bounds on Length of Boolean Formulas (1982) (33)
Secret Bit Transmission Using a Random Deal of Cards (1990) (32)
Circuit Size is Nonlinear in Depth (1975) (31)
Tighter Lower Bounds on the Exact Complexity of String Matching (1995) (31)
Strong spatial mixing for lattice graphs with fewer colours (2004) (30)
Faster circuits and shorter formulae for multiple addition, multiplication and symmetric Boolean functions (1990) (28)
The complexity of mean payo games on graphs (1996) (26)
A family of NFAs which need 2n- deterministic states (2003) (25)
The MINSUMCUT Problem (1991) (25)
Point Retrieval for Polygons (1986) (23)
Random sampling of 3-colorings in Z 2 (2004) (23)
A note on disjunctive form tautologies (1973) (23)
Wiretapping a hidden network (2009) (22)
Decision problems in computational models (1972) (22)
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols (2000) (22)
Random sampling of 3‐colorings in ℤ2 (2004) (22)
A proportionate fair scheduling rule with good worst-case performance (2003) (21)
Improved mixing bounds for the anti-ferromagnetic Potts model on Z^2 (2005) (20)
Fishspear: a priority queue algorithm (1994) (19)
Compact grid layouts of multi-level networks (1999) (19)
The asymptotic complexity of merging networks (1992) (19)
Shallow circuits and concise formulae for multiple addition and multiplication (1993) (18)
The Memory Game (1993) (18)
Contention resolution with bounded delay (1995) (17)
The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random (2004) (17)
Maximum overhang (2007) (17)
An Introduction to Boolean Function Complexity. (1976) (15)
Optimal tree layout (Preliminary Version) (1980) (15)
The Depth of All Boolean Functions (1975) (14)
Overhang (2007) (14)
New bounds on formula size (1977) (13)
Propositional Dynamic Logic is Weaker without Tests (1981) (13)
The complexity of choosing an H-colouring (nearly) uniformly at random (2002) (13)
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes (2014) (13)
Convergence of Opinion Diffusion is PSPACE-complete (2019) (13)
Lower bounds on the size of Boolean formulas: Preliminary Report (1975) (11)
Bounds on the Evaluation Time for Rational Polynomials (1971) (10)
Dense edge-disjoint embedding of binary trees in the mesh (1992) (10)
Computing voting power in easy weighted voting games (2008) (9)
Undecidability of PDL with L={a^(2i)|i>=0} (1984) (9)
The Planar Realization of Boolean Functions (1987) (9)
Combinatorial and computational aspects of multiple weighted voting games (2007) (8)
The complexity of gene placement (2001) (8)
Proceedings of the 17th International Colloquium on Automata, Languages and Programming (1990) (7)
On permutation communications in all-optical rings (1998) (7)
Layout of the batcher bitonic sorter (extended abstract) (1998) (7)
Layout of the Batcher Bitonic Sorter (1998) (7)
Storage Requirements for Fair Scheduling (1983) (7)
Poceedings of the London Mathematical Society symposium on Boolean function complexity (1992) (6)
Shallow multiplication circuits (1991) (6)
Tight Size Bounds for Packet Headers in Narrow Meshes (2000) (6)
Proceedings of the seventeenth international colloquium on Automata, languages and programming (1990) (6)
A Family of NFA's Which Need 2n -alpha Deterministic States (2000) (6)
Polynomial-Time Construction of Linear Network Coding (2008) (5)
On Weak Circular Squares in Binary Words (1997) (5)
Intersections of linear context-free languages and reversal-bounded multipushdown machines (Extended Abstract) (1974) (5)
Compact Grid Layouts of Some Multi-Level Networks (1999) (5)
Asymptotically Optimal Circuit for a Storage Access Function (1980) (4)
Universal Chains and Wiring Layouts (1988) (4)
Automata, Languages and Programming (1980) (4)
Classification of computationally tractable weighted voting games (2008) (4)
A Short Proof of the Dilation of a Toroidal Mesh in a Path (1993) (3)
David Michael Ritchie Park (1935-1990) in Memoriam (1994) (3)
Spanning connectivity games (2009) (3)
Multi-commodity Source Location Problems and Price of Greed (2008) (3)
Fishspear: A Priority Queue Algorithm (Extended Abstract) (1984) (3)
Evolution of an Algorithm (1993) (3)
Shallow multiplication circuits and wise financial investments (1992) (3)
Boolean Circuit Complexity (1992) (2)
Permutation Communication in All-Optical Rings (2002) (2)
A note on independence of a regularity-preserving operator (1970) (2)
Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions (1990) (2)
Dynamic monotone priorities on planar sets (1985) (2)
Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching (1993) (2)
More about Exact Slow $k$-Nim (2021) (1)
The complexity of choosing anH-colouring (nearly) uniformly at random (2002) (1)
Acknowledgments: We Would like to Thank 7.1 Renaming (1996) (1)
Complexity of some aspects of control and manipulation in weighted voting games (2008) (1)
Planar Acyclic Computation (1991) (1)
Combinatorial pattern matching : 10th Annual Symposium, CPM 99, Warwick University, UK, July 22-24, 1999 : proceedings (1999) (1)
Nearly optimal hierarchies for network and formula size (1986) (1)
Optimal embedding of a toroidal mesh in a path (1991) (1)
On Backtracking Resistance in Pseudorandom Bit Generation ∗ (2012) (1)
Automata, Languages and Programming (1990) (0)
On Abelian Circular Squares in Binary Words1 (2007) (0)
Which patterns are hard to find? (String matching) (1993) (0)
Looking for MUM and DAD: Text-Text Comparisons Do Help (1995) (0)
Dynamic Monotone Priorities on Planar Sets (Extended Abstract) (1985) (0)
Algorithms - ESA 2000 : 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000 : proceedings (2000) (0)
Book reviewAlgorithms: Their efficiency and complexity: By L. Kronsjö. Wiley, Chichester, 2nd ed., 1987, Price £24.95, ISBN 0471912018. (1988) (0)
BETTER APPROXIMATION GUARANTEESFOR JOB-SHOP SCHEDULING (2006) (0)
PIk mass production and an optimal circuit for the Nečiporuk slice (1993) (0)
Dense edge-disjoint embedding of complete binary trees in interconnection networks (2000) (0)
2 . There Exist Np Machines N 1 and N 2 Such That C = L(n (c) F Simulates N 1 on X by Substituting Query R of N 1 to L(n L 1 2 ) with Query (1993) (0)
Themes Complexity Theory ’ 94 In the months of August and September , 1994 (0)
Lower bound for monotone Boolean convolution (2017) (0)
The linear postman: a message-forwarding algorithm using sequential storage (1979) (0)
Obituary: Professor David Michael Ritchie Park (1990) (0)
Electronic Colloquium on Computational Complexity Lower Bounds for Monotone Span Programs (1995) (0)
Consistency of Natural Relations on Sets (1998) (0)
Techniques and Applications for ApproximatingString Distances { Rough Draft ( April 11 2000 ) (2007) (0)
Haystack Hunting Hints and Locker Room Communication (2020) (0)
Maximum Overhang (extended Abstract) (2007) (0)
Optimal Layout of Edge-weighted Forests (1999) (0)
Boolean Function Complexity: Preface (1992) (0)
Globe-hopping (2020) (0)
Automata, Languages and Programming 17th International Colloquium, Warwick University, England, July 16-20, 1990 : Proceedings (1990) (0)
Fishspear: A Priority Queue Algorithm1 (EXTENDED (1984) (0)
Analysis of Scheduling Algorithms for Proportionate Fairness (2004) (0)
Timed Modal Specifications........ 8 (0)
A Motivation of State Deenitions (0)
Maximizing the area of intersection of rectangles (2017) (0)
Without Merging (2020) (0)
M A ] 2 0 D ec 2 01 9 Convergence of Opinion Diffusion is PSPACE-complete (2019) (0)
Tight Size Bounds for Pa ket Headersin Narrow (2000) (0)
Matrix algorithms (2009) (0)
Combinatorial Communication in the Locker Room (2020) (0)
Variation in weighted voting games (2008) (0)
The Multi-Commodity Source Location Problems and the Price of Greed (2009) (0)
Decision problems in compputation models (1972) (0)

This paper list is powered by the following services:

Other Resources About Mike Paterson

en.wikipedia.org

What Schools Are Affiliated With Mike Paterson?

Mike Paterson is affiliated with the following schools:

Mike Paterson's Academic­Influence.com Rankings

Why Is Mike Paterson Influential?

Mike Paterson's Published Works

Published Works

Other Resources About Mike Paterson

What Schools Are Affiliated With Mike Paterson?

Mike Paterson's AcademicInfluence.com Rankings