Mike Paterson

Follow

Generating author description...

All published works
Action Title Year Authors
+ PDF Chat Haystack hunting hints and locker room communication 2022 Artur Czumaj
George Kontogeorgiou
Mike Paterson
+ More about Exact Slow $k$-Nim 2021 Nikolay Chikin
Vladimir Gurvich
Konstantin Knop
Mike Paterson
M. Vyalyi
+ Combinatorial Communication in the Locker Room 2020 Artur Czumaj
George Kontogeorgiou
Mike Paterson
+ Haystack Hunting Hints and Locker Room Communication 2020 Artur Czumaj
George Kontogeorgiou
Mike Paterson
+ PDF Chat Globe-hopping 2020 Dmitry Chistikov
Olga Goulko
Adrian Kent
Mike Paterson
+ PDF Chat Convergence of Opinion Diffusion is PSPACE-Complete 2020 Dmitry Chistikov
Grzegorz Lisowski
Mike Paterson
Paolo Turrini
+ Haystack Hunting Hints and Locker Room Communication 2020 Artur Czumaj
George Kontogeorgiou
Mike Paterson
+ Convergence of Opinion Diffusion is PSPACE-complete 2019 Dmitry Chistikov
Grzegorz Lisowski
Mike Paterson
Paolo Turrini
+ Convergence of Opinion Diffusion is PSPACE-complete 2019 Dmitry Chistikov
Grzegorz Lisowski
Mike Paterson
Paolo Turrini
+ Maximizing the area of intersection of rectangles 2017 D. B. A. Epstein
Mike Paterson
+ Lower bound for monotone Boolean convolution 2017 Mike Paterson
+ Improved upper bounds for Random-Edge and Random-Jump on abstract cubes 2013 Thomas Dueholm Hansen
Mike Paterson
Uri Zwick
+ PDF Chat False-Name Manipulations in Weighted Voting Games 2011 Haris Aziz
Yoram Bachrach
Edith Elkind
Mike Paterson
+ PDF Chat Wiretapping a Hidden Network 2009 Haris Aziz
Oded Lachish
Mike Paterson
Rahul Savani
+ Spanning connectivity games 2009 Haris Aziz
Oded Lachish
Mike Paterson
Rahul Savani
+ Wiretapping a hidden network 2009 Haris Aziz
Oded Lachish
Mike Paterson
Rahul Savani
+ False name manipulations in weighted voting games: splitting, merging and annexation 2009 Haris Aziz
Mike Paterson
+ Maximum overhang 2008 Mike Paterson
Yuval Peres
Mikkel Thorup
Peter Winkler
Uri Zwick
+ Computing voting power in easy weighted voting games 2008 Haris Aziz
Mike Paterson
+ On counting homomorphisms to directed acyclic graphs 2007 Martin Dyer
Leslie Ann Goldberg
Mike Paterson
+ Maximum overhang 2007 Mike Paterson
Yuval Peres
Mikkel Thorup
Peter Winkler
Uri Zwick
+ Maximum overhang 2007 Mike Paterson
Yuval Peres
Mikkel Thorup
Peter Winkler
Uri Zwick
+ Overhang 2007 Mike Paterson
Uri Zwick
+ On Counting Homomorphisms to Directed Acyclic Graphs 2006 Martin Dyer
Leslie Ann Goldberg
Mike Paterson
+ PDF Chat Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on <b>Z</b><sup>2</sup> 2006 Leslie Ann Goldberg
Markus Jalsenius
Russell Martin
Mike Paterson
+ Bounds for the growth rate of meander numbers 2005 Michael Albert
Mike Paterson
+ Improved mixing bounds for the anti-ferromagnetic Potts model on Z^2 2005 Leslie Ann Goldberg
Markus Jalsenius
Russell Martin
Mike Paterson
+ Strong Spatial Mixing with Fewer Colors for Lattice Graphs 2005 Leslie Ann Goldberg
Russell Martin
Mike Paterson
+ On counting homomorphisms to directed acyclic graphs 2005 Martin Dyer
Leslie Ann Goldberg
Mike Paterson
+ Strong Spatial Mixing for Lattice Graphs with Fewer Colours 2004 Leslie Ann Goldberg
Russell Martin
Mike Paterson
+ Random sampling of 3‐colorings in â„€<sup>2</sup> 2004 Leslie Ann Goldberg
Russell Martin
Mike Paterson
+ The Complexity of Choosing an <i>H</i>-Coloring (Nearly) Uniformly at Random 2004 Leslie Ann Goldberg
Steven Kelk
Mike Paterson
+ PDF Chat The computational complexity of two‐state spin systems 2003 Leslie Ann Goldberg
Mark Jerrum
Mike Paterson
+ The complexity of choosing an <i>H</i> -colouring (nearly) uniformly at random 2002 Leslie Ann Goldberg
Steven Kelk
Mike Paterson
+ The complexity of choosing an <i>H</i>-colouring (nearly) uniformly at random 2002 Leslie Ann Goldberg
Steven Kelk
Mike Paterson
+ PDF Chat Dense edge-disjoint embedding of complete binary trees in interconnection networks 2000 Somasundaram Ravindran
A.M. Gibbons
Mike Paterson
+ PDF Chat Consistency of Natural Relations on Sets 1998 Akira Maruoka
Mike Paterson
Hirotaka Koizumi
+ PDF Chat The asymptotic complexity of merging networks 1996 Peter Bro Miltersen
Mike Paterson
Jun Tarui
+ Poceedings of the London Mathematical Society symposium on Boolean function complexity 1992 Mike Paterson
+ PDF Chat The asymptotic complexity of merging networks 1992 Peter Bro Miltersen
Mike Paterson
Jun Tarui
+ PDF Chat The set of minimal braids is co-NP-complete 1991 Mike Paterson
Alexander Razborov
+ Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) 1981 Mike Paterson
Walter L. Ruzzo
Lawrence Snyder
+ Finding the median 1976 Arnold Schönhage
Mike Paterson
Nicholas Pippenger
+ A note on independence of a regularity-preserving operator 1970 Matthias Fischer
A. Meyer
Patrick E. OŚłNeil
Mike Paterson
Common Coauthors
Commonly Cited References
Action Title Year Authors # of times referenced
+ A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph 1995 Mark Jerrum
6
+ PDF Chat Random Walks on Combinatorial Objects 1999 Martin Dyer
Catherine Greenhill
6
+ Random generation of combinatorial structures from a uniform distribution 1986 Mark Jerrum
Leslie G. Valiant
Vijay V. Vazirani
5
+ Improved bounds for sampling colorings 2000 Eric Vigoda
5
+ Markov Chain Algorithms for Planar Lattice Structures 2001 Michael Luby
Dana Randall
Alistair Sinclair
5
+ The complexity of counting graph homomorphisms 2000 Martin Dyer
Catherine Greenhill
5
+ PDF Chat Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem 1997 JesĂșs Salas
Alan D. Sokal
5
+ Graph Homomorphisms and Phase Transitions 1999 Graham Brightwell
Peter Winkler
4
+ On Approximately Counting Colorings of Small Degree Graphs 1999 Russ Bubley
Martin Dyer
Catherine Greenhill
Mark Jerrum
4
+ None 2004 Christian Borgs
Jennifer Chayes
Stephan Mertens
Boris Pittel
4
+ Mixing in time and space for lattice spin systems: A combinatorial view 2004 Martin Dyer
Alistair Sinclair
Eric Vigoda
Dror Weitz
4
+ PDF Chat Path coupling: A technique for proving rapid mixing in Markov chains 2002 Russ Bubley
Martin Dyer
4
+ Mixing in time and space for discrete spin systems 2004 Dror Weitz
Alistair Sinclair
4
+ On the complexity of H-coloring 1990 Pavol Hell
Jaroslav Neơetƙil
4
+ Sampling Grid Colorings with Fewer Colors 2004 Dimitris Achlioptas
Mike Molloy
Cristopher Moore
Frank Van Bussel
3
+ The Complexity of Enumeration and Reliability Problems 1979 Leslie G. Valiant
3
+ Layered cross product&amp;mdashA technique to construct interconnection networks 1997 Shimon Even
Ami Litman
3
+ The complexity of partition functions 2005 AndreÄ­ A. Bulatov
Martin Grohe
3
+ Polynomial-Time Approximation Algorithms for the Ising Model 1993 Mark Jerrum
Alistair Sinclair
3
+ PDF Chat Comparison Theorems for Reversible Markov Chains 1993 Persi Diaconis
Laurent Saloff‐Coste
3
+ Towards a dichotomy theorem for the counting constraint satisfaction problem 2006 AndreÄ­ A. Bulatov
VĂ­ctor Dalmau
3
+ Random sampling of 3‐colorings in â„€<sup>2</sup> 2004 Leslie Ann Goldberg
Russell Martin
Mike Paterson
3
+ PDF Chat Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields 2001 Filippo Cesi
3
+ PSPACE-completeness of majority automata networks 2015 Éric Goles
Pedro Montealegre
Ville Salo
Ilkka TörmÀ
2
+ The complexity of H-colouring of bounded degree graphs 2000 Anna Galluccio
Pavol Hell
Jaroslav Neơetƙil
2
+ PDF Chat Social Networks with Competing Products 2014 Krzysztof R. Apt
Evangelos Markakis
2
+ A non-Markovian coupling for randomly sampling colorings 2004 Thomas P. Hayes
Eric Vigoda
2
+ Analyzing Glauber dynamics by comparison of Markov chains 2000 Dana Randall
Prasad Tetali
2
+ On Markov Chains for Independent Sets 2000 Martin Dyer
Catherine Greenhill
2
+ Approach to equilibrium of Glauber dynamics in the one phase region 1994 Fabio Martinelli
Enzo Olivieri
2
+ PDF Chat On randomly colouring locally sparse graphs 2006 Alan Frieze
Juan C. Vera
2
+ PDF Chat Randomly Coloring Constant Degree Graphs 2004 Martin Dyer
Alan Frieze
Thomas P. Hayes
Eric Vigoda
2
+ “Balls into Bins” — A Simple and Tight Analysis 1998 Martin Raab
Angelika Steger
2
+ PDF Chat The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree 2004 Michael Molloy
2
+ PDF Chat The computational complexity of two‐state spin systems 2003 Leslie Ann Goldberg
Mark Jerrum
Mike Paterson
2
+ PDF Chat Random walks on finite groups and rapidly mixing markov chains 1983 David Aldous
2
+ Strong Spatial Mixing with Fewer Colors for Lattice Graphs 2005 Leslie Ann Goldberg
Russell Martin
Mike Paterson
2
+ Fast mixing for independent sets, colorings and other models on trees 2004 Fabio Martinelli
Alistair Sinclair
Dror Weitz
2
+ Randomly coloring graphs of girth at least five 2003 Thomas P. Hayes
2
+ The Ising model on trees: boundary conditions and mixing time 2004 Fabio Martinelli
Alistair Sinclair
Dror Weitz
2
+ PDF Chat The logarithmic sobolev inequality for discrete spin systems on a lattice 1992 Daniel W. Stroock
BogusƂaw ZegarliƄski
2
+ PDF Chat Paradoxes in social networks with multiple products 2015 Krzysztof R. Apt
Evangelos Markakis
Sunil Simon
2
+ On Markov Chains for Randomly H-Coloring a Graph 2001 Colin Cooper
Martin Dyer
Alan Frieze
2
+ Randomly coloring graphs with lower bounds on girth and maximum degree 2003 Martin Dyer
Alan Frieze
2
+ On the computational complexity of the Jones and Tutte polynomials 1990 François Jaeger
Dirk Vertigan
Dominic Welsh
2
+ PDF Chat Lower Bounds on Merging Networks 1976 Andrew Chi-Chih Yao
Foong Frances Yao
2
+ Coupling with the stationary distribution and improved sampling for colorings and independent sets 2005 Tom Hayes
Eric Vigoda
2
+ Optimal attack and reinforcement of a network 1985 William H. Cunningham
2
+ Fractional arboricity, strength, and principal partitions in graphs and matroids 1992 Paul A. Catlin
Jerrold W. Grossman
Arthur M. Hobbs
Hong‐Jian Lai
2
+ On Counting Independent Sets in Sparse Graphs 2002 Martin Dyer
Alan Frieze
Mark Jerrum
2