Mike Paterson

According to our database1, Mike Paterson
  • authored at least 139 papers between 1970 and 2017.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Maximizing the area of intersection of rectangles.
CoRR, 2017

2014
False-Name Manipulations in Weighted Voting Games.
CoRR, 2014

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2011
False-Name Manipulations in Weighted Voting Games.
J. Artif. Intell. Res., 2011

2009
Overhang.
The American Mathematical Monthly, 2009

Maximum Overhang.
The American Mathematical Monthly, 2009

The Multi-Commodity Source Location Problems and the Price of Greed.
J. Graph Algorithms Appl., 2009

Wiretapping a hidden network
CoRR, 2009

Spanning connectivity games
CoRR, 2009

False name manipulations in weighted voting games: splitting, merging and annexation
CoRR, 2009

Wiretapping a Hidden Network.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

False name manipulations in weighted voting games: splitting, merging and annexation.
Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), 2009

Power Indices in Spanning Connectivity Games.
Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008
A Deterministic Subexponential Algorithm for Solving Parity Games.
SIAM J. Comput., 2008

Computing voting power in easy weighted voting games
CoRR, 2008

Multi-commodity Source Location Problems and Price of Greed.
Proceedings of the WALCOM: Algorithms and Computation, Second International Workshop, 2008

Maximum overhang.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Polynomial-Time Construction of Linear Network Coding.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
On counting homomorphisms to directed acyclic graphs.
J. ACM, 2007

2006
Overhang.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A deterministic subexponential algorithm for solving parity games.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

On Counting Homomorphisms to Directed Acyclic Graphs.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
Strong Spatial Mixing with Fewer Colors for Lattice Graphs.
SIAM J. Comput., 2005

On counting homomorphisms to directed acyclic graphs
Electronic Colloquium on Computational Complexity (ECCC), 2005

2004
The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random.
SIAM J. Comput., 2004

A bound on the capacity of backoff and acknowledgment-based protocols.
SIAM J. Comput., 2004

Random sampling of 3-colorings in Z2.
Random Struct. Algorithms, 2004

Analysis of Scheduling Algorithms for Proportionate Fairness.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

trong Spatial Mixing for Lattice Graphs with Fewer Colours.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
A family of NFAs which need 2n- deterministic states.
Theor. Comput. Sci., 2003

The computational complexity of two-state spin systems.
Random Struct. Algorithms, 2003

A proportionate fair scheduling rule with good worst-case performance.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

2002
Permutation Communication in All-Optical Rings.
Parallel Processing Letters, 2002

The complexity of choosing an H-colouring (nearly) uniformly at random.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
Better Approximation Guarantees for Job-Shop Scheduling.
SIAM J. Discrete Math., 2001

The Complexity of Gene Placement.
J. Algorithms, 2001

2000
Dense edge-disjoint embedding of complete binary trees in interconnection networks.
Theor. Comput. Sci., 2000

Contention resolution with constant expected delay.
J. ACM, 2000

Communication complexity of document exchange.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A Family of NFA's Which Need 2n -alpha Deterministic States.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Tight Size Bounds for Packet Headers in Narrow Meshes.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
SIAM J. Comput., 1999

The chip in your wallet - The technology of security in smartcard chip manufacture.
Inf. Sec. Techn. Report, 1999

Optimal Layout of Edge-weighted Forests.
Discrete Applied Mathematics, 1999

Compact Grid Layouts of Multi-Level Networks.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

The Complexity of Gene Placement.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
Consistency of Natural Relations on Sets.
Combinatorics, Probability & Computing, 1998

Layout of the Batcher Bitonic Sorter (Extended Abstract).
SPAA, 1998

On Approximating Rectangle Tiling and Packing.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

On permutation communications in all-optical rings.
Proceedings of the SIROCCO'98, 1998

1997
On Nearest-Neighbor Graphs.
Discrete & Computational Geometry, 1997

Lower Bounds for Monotone Span Programs.
Computational Complexity, 1997

Better Approximation Guarantees for Job-shop Scheduling.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

On Weak Circular Squares in Binary Words.
Proceedings of the Combinatorial Pattern Matching, 8th Annual Symposium, 1997

1996
The Complexity of Mean Payoff Games on Graphs.
Theor. Comput. Sci., 1996

The Asymptotic Complexity of Merging Networks.
J. ACM, 1996

On the Complexity of String Folding.
Discrete Applied Mathematics, 1996

Progress in Selection.
Proceedings of the Algorithm Theory, 1996

On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics).
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On the Complexity of String Folding.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Tighter Lower Bounds on the Exact Complexity of String Matching.
SIAM J. Comput., 1995

Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences.
Random Struct. Algorithms, 1995

The Complexity of Mean Payoff Games on Graphs
Electronic Colloquium on Computational Complexity (ECCC), 1995

Lower Bounds for Monotone Span Programs
Electronic Colloquium on Computational Complexity (ECCC), 1995

PIk Mass Production and an Optimal Circuit for the Neciporuk Slice.
Computational Complexity, 1995

Looking for MUM and DAD: Text-Text Comparisons Do Help.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Contention Resolution with Bounded Delay.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Lower Bounds for Monotone Span Programs.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

The Complexity of Mean Payoff Games.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994
David Michael Ritchie Park (1935-1990) in Memoriam.
Theor. Comput. Sci., 1994

Fishspear: A Priority Queue Algorithm.
J. ACM, 1994

Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences.
Proceedings of the STACS 94, 1994

Longest Common Subsequences.
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

1993
The Memory Game.
Theor. Comput. Sci., 1993

Shrinkage of de Morgan Formulae under Restriction.
Random Struct. Algorithms, 1993

A Short Proof of the Dilation of a Toroidal Mesh in a Path.
Inf. Process. Lett., 1993

Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication.
Computational Complexity, 1993

Which Patterns are Hard to Find?
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Evolution of an Algorithm.
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992
Optimal Binary Space Partitions for Orthogonal Objects.
J. Algorithms, 1992

Shallow Multiplication Circuits and Wise Financial Investments
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Dense Edge-Disjoint Embedding of Binary Trees in the Mesh.
SPAA, 1992

Boolean Circuit Complexity.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

On Nearest-Neighbor Graphs.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

The Asymptotic Complexity of Merging Networks
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Planar Acyclic Computation
Inf. Comput., February, 1991

The Set of Minimal Braids is co-NP-Complete.
J. Algorithms, 1991

The MINSUMCUT Problem.
Proceedings of the Algorithms and Data Structures, 1991

Shrinkage of de~Morgan formulae under restriction
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling.
Discrete & Computational Geometry, 1990

Improved Sorting Networks with O(log N) Depth.
Algorithmica, 1990

Computing Euclidean Maximum Spanning Trees.
Algorithmica, 1990

Optimal Binary Space Partitions for Orthogonal Objects.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Partitioning Space for Range Queries.
SIAM J. Comput., 1989

Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988
Universal Chains and Wiring Layouts.
SIAM J. Discrete Math., 1988

Computing Euclidean Maximum Spanning Trees.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987
The Planar Realization of Boolean Functions.
Inf. Process. Lett., 1987

1986
Point Retrieval for Polygons.
J. Algorithms, 1986

Nearly Optimal Hierarchies for Network and Formula Size.
Acta Inf., 1986

1985
Impossibility of Distributed Consensus with One Faulty Process
J. ACM, April, 1985

Dynamic Monotone Priorities on Planar Sets (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Undecidability of PDL with L={a^(2i)|i>=0}.
J. Comput. Syst. Sci., 1984

Fishspear: A Priority Queue Algorithm (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Storage Requirements for Fair Scheduling.
Inf. Process. Lett., 1983

Impossibility of Distributed Consensus with One Faulty Process.
Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1983

1982
Omega(n log n) Lower Bounds on Length of Boolean Formulas.
SIAM J. Comput., 1982

Efficient Parallel Algorithms for Linear Recurrence Computation.
Inf. Process. Lett., 1982

1981
Propositional Dynamic Logic is Weaker without Tests.
Theor. Comput. Sci., 1981

Optimal Packing and Covering in the Plane are NP-Complete.
Inf. Process. Lett., 1981

Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract)
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980
Selection and Sorting with Limited Storage.
Theor. Comput. Sci., 1980

Asymtotically Optimal Circuit for a Storage Access Function.
IEEE Trans. Computers, 1980

A Faster Algorithm Computing String Edit Distances.
J. Comput. Syst. Sci., 1980

Optimal Tree Layout (Preliminary Version)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
The linear postman: a message-forwarding algorithm using sequential storage.
Proceedings of the Algorithms in Modern Mathematics and Computer Science, 1979

1978
Linear Unification.
J. Comput. Syst. Sci., 1978

Selection and Sorting with Limited Storage
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977
The Depth of All Boolean Functions.
SIAM J. Comput., 1977

New bounds on formula size.
Proceedings of the Theoretical Computer Science, 1977

1976
Circuit Size is Nonlinear in Depth.
Theor. Comput. Sci., 1976

Finding the Median.
J. Comput. Syst. Sci., 1976

Linear Unification
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

1975
Complexity of Monotone Networks for Boolean Matrix Product.
Theor. Comput. Sci., 1975

Deterministic One-Counter Automata.
J. Comput. Syst. Sci., 1975

Lower Bounds on the Size of Boolean Formulas: Preliminary Report
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974
Reversal-Bounded Acceptors and Intersections of Linear Languages.
SIAM J. Comput., 1974

Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract)
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials.
SIAM J. Comput., 1973

Optimal Algorithms for Parallel Polynomial Evaluation.
J. Comput. Syst. Sci., 1973

Deterministic one-counter automata.
Proceedings of the 1. Fachtagung über Automatentheorie und Formale Sprachen, 1973

1972
Tape Bounds for Time-Bounded Turing Machines.
J. Comput. Syst. Sci., 1972

Decision problems in computational models.
Proceedings of the International Sympoisum on Theoretical Programming, 1972

1971
Bounds on the Evaluation Time for Rational Polynomials
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

Optimal Algorithms for Parallel Polynomial Evaluation
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971

1970
On Formalised Computer Programs.
J. Comput. Syst. Sci., 1970

Tape-Bounds for Time-Bounded Turing Machines
Proceedings of the 11th Annual Symposium on Switching and Automata Theory, 1970


  Loading...