Mike S. Paterson

Available identifiers

zbMath Open paterson.mike-sWikidataQ1659753 ScholiaQ1659753MaRDI QIDQ1904666

List of research outcomes

Publication	Date of Publication	Type
The complexity of mean payoff games	2023-12-12	Paper
Haystack hunting hints and locker room communication	2023-10-23	Paper
Progress in selection	2022-12-09	Paper
Longest common subsequences	2022-08-18	Paper
Bounded Hanoi	2022-04-22	Paper
More about Exact Slow $k$-Nim	2022-03-24	Paper
Globe-hopping	2021-10-29	Paper
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes	2019-06-20	Paper
Looking for MUM and DAD: Text-text comparisons do help	2017-01-19	Paper
https://portal.mardi4nfdi.de/entity/Q5501839	2015-08-14	Paper
Maximum Overhang	2012-01-01	Paper
False-Name Manipulations in Weighted Voting Games	2011-01-21	Paper
A deterministic subexponential algorithm for solving parity games	2010-08-16	Paper
Overhang	2010-08-16	Paper
https://portal.mardi4nfdi.de/entity/Q3579383	2010-08-06	Paper
The complexity of choosing an H -colouring (nearly) uniformly at random	2010-08-05	Paper
A Deterministic Subexponential Algorithm for Solving Parity Games	2009-08-20	Paper
Power Indices in Spanning Connectivity Games	2009-07-02	Paper
The Multi-Commodity Source Location Problems and the Price of Greed	2009-05-19	Paper
On Counting Homomorphisms to Directed Acyclic Graphs	2009-03-12	Paper
Overhang	2009-02-26	Paper
On counting homomorphisms to directed acyclic graphs	2008-12-21	Paper
Polynomial-Time Construction of Linear Network Coding	2008-08-28	Paper
Multi-commodity Source Location Problems and Price of Greed	2008-03-25	Paper
Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²	2007-04-04	Paper
Contention resolution with constant expected delay	2006-09-12	Paper
Strong Spatial Mixing with Fewer Colors for Lattice Graphs	2006-06-01	Paper
A Bound on the Capacity of Backoff and Acknowledgment-Based Protocols	2005-02-21	Paper
The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random	2005-02-21	Paper
https://portal.mardi4nfdi.de/entity/Q4818874	2004-09-24	Paper
Random sampling of 3‐colorings in ℤ²	2004-08-06	Paper
The computational complexity of two‐state spin systems	2003-11-10	Paper
A family of NFAs which need 2$^{n}-\alpha$ deterministic states	2003-07-30	Paper
The Complexity of Gene Placement	2002-07-08	Paper
https://portal.mardi4nfdi.de/entity/Q4536379	2002-06-25	Paper
https://portal.mardi4nfdi.de/entity/Q4230345	2002-01-17	Paper
https://portal.mardi4nfdi.de/entity/Q2754194	2001-12-09	Paper
https://portal.mardi4nfdi.de/entity/Q2754189	2001-11-11	Paper
Better Approximation Guarantees for Job-Shop Scheduling	2001-03-19	Paper
https://portal.mardi4nfdi.de/entity/Q4952617	2000-05-10	Paper
https://portal.mardi4nfdi.de/entity/Q4231915	2000-04-26	Paper
https://portal.mardi4nfdi.de/entity/Q4942627	2000-03-16	Paper
https://portal.mardi4nfdi.de/entity/Q4252311	1999-09-15	Paper
Consistency of Natural Relations on Sets	1999-09-05	Paper
https://portal.mardi4nfdi.de/entity/Q4252753	1999-08-31	Paper
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)	1999-02-22	Paper
The asymptotic complexity of merging networks	1998-01-19	Paper
Lower bounds for monotone span programs	1997-09-07	Paper
The complexity of mean payoff games on graphs	1997-02-27	Paper
On the complexity of string folding	1997-02-25	Paper
https://portal.mardi4nfdi.de/entity/Q4875208	1997-01-05	Paper
Upper bounds for the expected length of a longest common subsequence of two binary sequences	1996-05-28	Paper
$\text{PI}_ k$ mass production and an optimal circuit for the Nečiporuk slice	1996-05-27	Paper
Tighter Lower Bounds on the Exact Complexity of String Matching	1995-03-27	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Mike S. Paterson