Mike Paterson
According to our database^{1},
Mike Paterson
authored at least 121 papers
between 1970 and 2014.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at id.loc.gov

at dnb.info

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
2014
Improved upper bounds for RandomEdge and RandomJump on abstract cubes.
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
2011
FalseName Manipulations in Weighted Voting Games.
J. Artif. Intell. Res., 2011
2009
The MultiCommodity Source Location Problems and the Price of Greed.
J. Graph Algorithms Appl., 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
Multicommodity 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 ACMSIAM Symposium on Discrete Algorithms, 2008
PolynomialTime Construction of Linear Network Coding.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
2006
Overhang.
Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms, 2006
A deterministic subexponential algorithm for solving parity games.
Proceedings of the Seventeenth Annual ACMSIAM 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 HColoring (Nearly) Uniformly at Random.
SIAM J. Comput., 2004
A bound on the capacity of backoff and acknowledgmentbased protocols.
SIAM J. Comput., 2004
Random sampling of 3colorings in Z^{2}.
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 twostate spin systems.
Random Struct. Algorithms, 2003
A proportionate fair scheduling rule with good worstcase performance.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003
2002
Permutation Communication in AllOptical Rings.
Parallel Processing Letters, 2002
The complexity of choosing an Hcolouring (nearly) uniformly at random.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
2000
Dense edgedisjoint 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 ACMSIAM Symposium on Discrete Algorithms, 2000
A Family of NFA's Which Need 2^{n} alpha Deterministic States.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000
A Bound on the Capacity of Backoff and AcknowledgementBased 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 Edgeweighted Forests.
Discrete Applied Mathematics, 1999
Compact Grid Layouts of MultiLevel Networks.
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
The Complexity of Gene Placement.
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
1998
Consistency of Natural Relations on Sets.
Combinatorics, Probability & Computing, 1998
Layout of the Batcher Bitonic Sorter (Extended Abstract).
Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998
On Approximating Rectangle Tiling and Packing.
Proceedings of the Ninth Annual ACMSIAM Symposium on Discrete Algorithms, 1998
On permutation communications in alloptical rings.
Proceedings of the SIROCCO'98, 1998
1997
On NearestNeighbor Graphs.
Discrete & Computational Geometry, 1997
Better Approximation Guarantees for Jobshop Scheduling.
Proceedings of the Eighth Annual ACMSIAM 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
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 ACMSIAM 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
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
PI_{k} Mass Production and an Optimal Circuit for the Neciporuk Slice.
Computational Complexity, 1995
Looking for MUM and DAD: TextText 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 (19351990) 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
Shallow Multiplication Circuits and Wise Financial Investments
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
Dense EdgeDisjoint Embedding of Binary Trees in the Mesh.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992
Boolean Circuit Complexity.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992
On NearestNeighbor 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 coNPComplete.
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 HiddenSurface Removal and Solid Modeling.
Discrete & Computational Geometry, 1990
Improved Sorting Networks with O(log N) Depth.
Algorithmica, 1990
Optimal Binary Space Partitions for Orthogonal Objects.
Proceedings of the First Annual ACMSIAM 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 SIGACTSIGMOD 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 NPComplete.
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 messageforwarding 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
Lower Bounds on the Size of Boolean Formulas: Preliminary Report
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975
1974
ReversalBounded Acceptors and Intersections of Linear Languages.
SIAM J. Comput., 1974
Intersections of Linear ContextFree Languages and ReversalBounded 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 onecounter automata.
Proceedings of the 1. Fachtagung über Automatentheorie und Formale Sprachen, 1973
1972
Tape Bounds for TimeBounded 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
TapeBounds for TimeBounded Turing Machines
Proceedings of the 11th Annual Symposium on Switching and Automata Theory, 1970