Wiretapping a hidden network (2009)
Aziz, Haris, Lachish, Oded, Paterson, Mike, Savani, Rahul
We consider the problem of maximizing the probability of hitting a strategically chosen hidden virtual network by placing a wiretap on a single link of a communication network. This can be seen as a...
Spanning connectivity games (2009)
Aziz, Haris, Lachish, Oded, Paterson, Mike, Savani, Rahul
The Banzhaf index, Shapley-Shubik index and other voting power indices measure the importance of a player in a coalitional game. We consider a simple coalitional game called the spanning connectivity...
False name manipulations in weighted voting games: splitting, merging and annexation (2009)
An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name...
How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of 1
Strong spatial mixing with fewer colours for lattice graphs (2008)
Leslie Ann Goldberg, Russell Martin, Mike Paterson
Abstract Recursively-constructed couplings have been used in the past for mixing on trees. We show how to extend this technique to non-tree-like graphs such as lattices. Using this method, we obtain...
Abstract Maximum Overhang (extended abstract) ∗ (2008)
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Computing voting power in easy weighted voting games (2008)
Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model...
Random Sampling of 3-colourings in Z 2 * (2008)
Leslie Ann Goldberg, Russell Martin, Mike Paterson
We consider the problem of uniformly sampling proper 3-colourings of an m×n rectangular region of Z 2. We show that the single-site “Glauber-dynamics ” Markov chain is rapidly mixing. Our result...
with Good Worst-case Performance ∗ (2008)
Scheduling Rule, Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg, ...
In this paper we consider the following scenario. A set of n jobs with different threads is being run concurrently. Each job has an associated weight, which gives the proportion of processor time...
The Complexity of Gene Placement (2008)
Leslie Ann, Goldberg Paul, W. Goldberg, Mike Paterson, Pavel Pevzner, Süleyman Cenk, ...
along a strand of its DNA. The goal is to construct, We focus on algorithmic problems related to deriv- for each species, a sequence in which the genes occur ing gene locations on DNA sequences of...
Strong spatial mixing with fewer colours for lattice graphs (2008)
Leslie Ann Goldberg, Russell Martin, Mike Paterson
Recursively-constructed couplings have been used in the past for mixing on trees. We show how to extend this technique to non-tree-like graphs such as lattices. Using this method, we obtain the...
A bound on the capacity of backoff and acknowledgement-based protocols (2008)
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson
Abstract. We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, λ, is at least 0.42 and that the capacity of...
Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson
To the memory of Paul Erdos and to his living heritage Abstract. An abelian square in a binary word is a pair of adjacent nonempty blocks of the same length, having the same number of 1s. An abelian...
Techniques and Applications for Approximating String Distances -- Rough Draft (April 11 2000) (2007)
Graham Cormode Muthukrishnan, S. Muthukrishnan, Mike Paterson, Suleyman Cenk S
this paper, we introduce techniques which allow us to approximate the distance between strings under a variety of distance measures. The first technique is Hamming Signatures, which computes an O(log...
The Complexity of Gene Placement (2007)
Leslie Ann, Paul W. Goldberg, Mike Paterson, Pavel Pevzner, Elizabeth Sweedyk
We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on...
Looking for MUM and DAD: text-text comparisons do help (2007)
Mike Paterson, Shlomit Tassa, Uri Zwick
. It is known that about 4n 3 comparisons are needed, in the worst case, to find all the occurrences of the string aba in a text of length n if only pattern--text comparisons are allowed. We show...
Consistency of Natural Relations on Sets (2007)
Hirotaka Koizumi, Akira Maruoka, Mike Paterson, Gamma N
The natural relations for sets are those definable in terms of the emptiness of the subsets corresponding to Boolean combinations of the sets. For pairs of sets, there are just five natural relations...
The Complexity of Gene Placement (2007)
Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk
We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on...
On Weak Circular Squares in Binary Words (2007)
Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson
. A weak square in a binary word is a pair of adjacent nonempty blocks of the same length, having the same number of 1s. A weak circular square is a weak square which is possibly wrapped around the...
The computational complexity of two-state spin systems* (2007)
The subject of this article is spin-systems as studied in statistical physics. We focus on the case of two spins. This case encompasses models of physical interest, such as the classical Ising model...
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
The paper considers the exact number of character comparisons needed to nd all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms,...
Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability...
The Complexity of Gene Placement (2007)
Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel Pevzner, Elizabeth Sweedyk
We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on...
How far off the edge of the table can we reach by stacking $n$ identical, homogeneous, frictionless blocks of length 1? A classical solution achieves an overhang of $1/2 H_n$, where $H_n ~ \ln n$ is...
Paterson, Mike, Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri
How far can a stack of $n$ identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
A deterministic subexponential algorithm for solving parity games (2006)
Marcin Jurdziński, Mike Paterson, Uri Zwick
The existence of polynomial time algorithms for the solution of parity games is a major open problem. The fastest known algorithms for the problem are randomized algorithms that run in subexponential...
Paul Spirakis Greece, Catuscia Palamidessi France, Maurice Nivat, Mike Paterson, Arto Salomaa, Grzegorz Rozenberg
On counting homomorphisms to directed acyclic graphs (2006)
Martin Dyer, Leslie Ann Goldberg, Mike Paterson
It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes which lie strictly between them. Thus, if P ≠ NP, it is not possible to classify NP...
Improved mixing bounds for the Anti-Ferromagnetic Potts 2 ∗ Model on Z (2006)
Leslie Ann Goldberg, Markus Jalsenius, Russell Martin, Mike Paterson
We consider the anti-ferromagnetic Potts model on the the integer lattice Z 2. The model has two parameters, q, the number of spins, and λ = exp(−β), where β is “inverse temperature”. It is...
Paul Spirakis Greece, Wilfried Brauer Germany, Catuscia Palamidessi France, Maurice Nivat, Mike Paterson, Arto Salomaa, ...
Improved mixing bounds for the anti-ferromagnetic Potts model on Z^2 (2005)
Goldberg, Leslie Ann, Jalsenius, Markus, Martin, Russell, Paterson, Mike
We consider the anti-ferromagnetic Potts model on the the integer lattice Z^2. The model has two parameters, q, the number of spins, and \lambda=\exp(-\beta), where \beta is ``inverse temperature''....
A Proportionate Fair Scheduling Rule with Good Worst-case Performance\Lambda (2004)
Micah Adlery, Petra Berenbrinkz, Tom Friedetzkyx, Leslie Ann Goldberg, Paul Goldberg, Mike Paterson
Abstract In this paper we consider the following scenario. A set of n jobs with different threads is being run concurrently. Each job has an associated weight, which gives the proportion of processor...
Randomised Algorithms: a Computational Approach ” and the IST Programme of the EU (2003)
Leslie Ann Goldberg, Steven Kelk, Mike Paterson
Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. Special cases of this problem include sampling colourings and independent sets and sampling from...
Leslie Ann Goldberg, Sampath Kannan, Mark Jerrum, Mike Paterson
We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, λ, is at least 0.42 and that the capacity of every...
The complexity of choosing an H-colouring (nearly) uniformly at random (2002)
Leslie Ann Goldberg, Steven Kelk, Mike Paterson
Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. They considered the family of \cautious " ergodic Markov chains with uniform stationary...
The complexity of choosing an H-colouring (nearly) uniformly at random (2001)
Leslie Ann Goldberg, Steven Kelk, Mike Paterson
Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. Special cases of this problem include sampling colourings and independent sets and sampling from...
Tight Size Bounds for Packet Headers in Narrow Meshes (2000)
Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson
. Consider the problem of sending a single message from a sender to a receiver through an m n mesh with asynchronous links that may stop working, and memoryless intermediate nodes. We prove that for...
Communication Complexity of Document Exchange (2000)
Graham Cormode Mike, Mike Paterson, Suleyman Cenk S
We address the problem of minimizing the communication involved in the exchange of similar documents. We consider two users, A and B, who hold documents x and y respectively. Neither of the users has...
Communication Complexity of Document Exchange (2000)
Graham Cormode, Mike Paterson, Suleyman Cenk Sahinalp, Uzi Vishkin, Suleyman Cenk S
We address the problem of minimizing the communication involved in the exchange of similar documents. We consider two users, A and B, who hold documents x and y respectively. Neither of the users has...
Tight Size Bounds for Packet Headers in Narrow Meshes (2000)
Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson
. Consider the problem of sending a single message from a sender to a receiver through an m n mesh with asynchronous links that may stop working, and memoryless intermediate nodes. We prove that for...
Tight Size Bounds for Packet Headers in Narrow Meshes (2000)
Micah Adler Faith, Faith Fich, Leslie Ann Goldberg, Mike Paterson
. Consider the problem of sending a single message from a sender to a receiver through an m n mesh with asynchronous links that may stop working, and memoryless intermediate nodes. We prove that for...
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols (2000)
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Goldberg Mark, Jerrum Sampath Kannan, Mike Paterson
We study contention-resolution protocols for multiple-access channels. We show that every backo protocol is transient if the arrival rate, , is at least 0:42 and that the capacity of every backo...
Resource Constrained Shortest Paths (2000)
Mehlhorn, Kurt, Ziegelmann, Mark, Paterson, Mike
The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and...
Lower bounds for monotone span programs (1999)
Anna G Al, Amos Beimel, Amos Beimel, Mike Paterson, Mike Paterson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Lower bounds for monotone span programs (1999)
Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs and for contact schemes. Monotone span...
Compact Grid Layouts of Multi-Level Networks (1999)
S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel
We consider the problem of generating layouts of multilevel networks, in particular, switching, sorting, and interconnection networks, as compactly as possible on VLSI grids. Besides traditional...
The Complexity of Gene Placement (1999)
Leslie Ann Goldberg, Paul W. Goldberg, Pavel Pevzner, Mike Paterson, Elizabeth Sweedyk
We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on...
The complexity of gene placement (1999)
Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel Pevzner, Süleyman Cenk Sahinalp
We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on...
The complexity of gene placement (1999)
Leslie Ann Goldberg, Paul W. Goldberg, Pavel Pevzner, Mike Paterson, Elizabeth Sweedyk
We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on...
On Permutation Communications in All-Optical Rings (1998)
Mike Paterson, Heiko Schröder, Ondrej Sykora, Imrich Vrto
We study the wavelength problem and arc (edge) congestion problem for communicating permutation instances on a ring. We prove that the numbers of wavelengths in the directed case ! w , in the...
Contention Resolution with Constant Expected Delay (1998)
Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability...
On Permutation Communications in All-Optical Rings (1998)
Mike Paterson, Heiko Schröder, Ondrej Sykora, Imrich Vrto
We study the wavelength problem and arc (edge) congestion problem for communicating permutation instances on a ring. We prove that the numbers of wavelengths in the directed case \Gamma! w , in the...
On Permutation Communications in All-Optical Rings (Extended Abstract) (1998)
Mike Paterson, Heiko Schröder, Ondrej Sykora, Imrich Vrto, Imrich Vr To
Research Submission) Mike Paterson Heiko Schroder y Ondrej S'ykora z Imrich Vr to z Abstract We study the wavelength problem and arc (edge) congestion problem for communicating permutation...
Better approximation guarantees for job-shop scheduling (1997)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Abstract. Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic)...
Lower Bounds For Monotone Span Programs (1997)
Amos Beimel, Anna Gál, Anna G Al, Mike Paterson
. Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs and for contact schemes. Monotone...
Lower Bounds for Monotone Span Programs (1997)
Amos Beimel, Anna Gál, Mike Paterson
Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs and for contact schemes. Monotone span...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1997)
Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup
We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = min T fk T \Gamma D...
. There has been recent progress in the selection problem, and in median-finding in particular, after a lull of ten years. This paper reviews some ancient and modern results on this problem, and...
Better Approximation Guarantees for Job-shop Scheduling (1997)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein &Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic)...
On the Complexity of String Folding (1996)
Mike Paterson, Coventry Cv Al, Teresa Przytycka
A fold of a finite string S over a given alphabet is an embedding of S in some fixed infinite grid, such as the square or cubic mesh. The score of a fold is the number of pairs of matching string...
On the Complexity of String Folding (1996)
Mike Paterson, Teresa Przytycka
Introduction The motivation for the string-folding problems considered here lies in computational biology. Prediction of the three-dimensional structure of a protein from its known linear sequence of...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1996)
Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup
. We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric under the L1 norm, that is, " = minT fk T \Gamma D...
The Complexity of Mean Payoff Games on Graphs (1996)
We study the complexity of finding the values and optimal strategies of mean payoff games on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski and considered by...
Better Approximation Guarantees for Job-Shop Scheduling (1996)
Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein & Wein presented the rst polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation...
The Asymptotic Complexity of Merging Networks (1996)
Peter Bro Miltersen, Mike Paterson
Abstract. Let Mm, n) be the minimum number of comparators needed in a comparator network that merges m elements x, < x2 zz... ZG x, and n elements y, 5 y, <... s y,, where n t m. Batcher’s...
Contention resolution with bounded delay (1995)
Mike Paterson, Aravind Srinivasan
When distributed processes contend for a shared resource, we need a good distributed contention resolution protocol, e.g., for multiple-access channels (ALOHA, Ethernet), PRAM emulation, and optical...
The Asymptotic Complexity of Merging Networks (Extended Abstract) (1995)
Peter Bro Miltersen, Mike Paterson
) Peter Bro Miltersen y Mike Paterson z Jun Tarui z January 16, 1995 Abstract Let M (m; n) be the minimum number of comparators in a comparator network that merges two ordered chains x 1 x 2 : : : xm...
Tighter Lower Bounds on the Exact Complexity of String Matching (1995)
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
. The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line...
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1995)
Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup
We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric, that is, " = min T fk T; D k1 g. First we present...
Lower Bounds for Monotone Span Programs (1995)
Amos Beimel, Anna Gál, Mike Paterson
. The model of span programs is a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for contact schemes, symmetric branching programs and for formula size....
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics) (1995)
Richa Agarwala, Vineet Bafna, Martin Farach, Babu Narayanan, Mike Paterson, Mikkel Thorup
We consider the problem of fitting an n \Theta n distance matrix D by a tree metric T . Let " be the distance to the closest tree metric, that is, " = min T fk T; D k1 g. First we present...
Longest Common Subsequences (1994)
. The length of a longest common subsequence (LLCS) of two or more strings is a useful measure of their similarity. The LLCS of a pair of strings is related to the `edit distance', or number of...
The Asymptotic Complexity of Merging Networks (1992)
Peter Bro Miltersen, Mike Paterson, Jun Tarui, Coventry Cv Al
Let M (m; n) be the minimum number of comparators needed in a comparator network that merges m elements x 1 x 2 : : : xm and n elements y 1 y 2 : : : y n , where n m. Batcher's odd-even merge...
Combinatorial and computational aspects of multiple weighted voting games
Aziz, Haris, Paterson, Mike, Leech, Dennis
Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model...
On Approximating Rectangle Tiling and Packing
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and...
Contention Resolution with Constant Expected Delay
Leslie Ann, Philip D. Mackenzie, Mike Paterson, Aravind Srinivasan
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability...
A Bound on the Capacity of Backo and Acknowledgement-Based Protocols
Leslie Ann Goldberg, Goldberg Mark, Jerrum Sampath Kannan, Mike Paterson
We study contention-resolution protocols for multiple-access channels. We show that every backo protocol is transient if the arrival rate, , is at least 0:42 and that the capacity of every backo...
On Approximating Rectangle Tiling and Packing
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and...
Amos Beimel, Anna Gál, Mike Paterson, Amos Beimel, Anna Gál, Mike Paterson
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
On Approximating Rectangle Tiling and Packing
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and...