Mike Paterson - RankMe

154 papers A* 35A 4B 12C 1Misc 1Journal 84Unranked 16

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Variance Dichotomy in Feature Spaces of Facial Recognition Systems is a Weak Defense against Simple Weight Manipulation Attacks. Trans. Mach. Learn. Res. Matthew Bowditch, Mike Paterson, Matthias Englert, Ranko Lazic
2024	A	`conf`	Learning a Social Network by Influencing Opinions. AAMAS Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini
2023	J	`jnl`	Haystack hunting hints and locker room communication. Random Struct. Algorithms Artur Czumaj, George Kontogeorgiou, Mike Paterson
2022	J	`jnl`	Bounded Hanoi. Am. Math. Mon. Kazuo Iwama, Mike Paterson
2021	A*	`conf`	Haystack Hunting Hints and Locker Room Communication. ICALP Artur Czumaj, George Kontogeorgiou, Mike Paterson
2020	J	`jnl`	Combinatorial Communication in the Locker Room. CoRR Artur Czumaj, George Kontogeorgiou, Mike Paterson
2020	A*	`conf`	Convergence of Opinion Diffusion is PSPACE-Complete. AAAI Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini
2020	J	`jnl`	Globe-hopping. CoRR Dmitry Chistikov, Olga Goulko, Adrian Kent, Mike Paterson
2019	J	`jnl`	Convergence of Opinion Diffusion is PSPACE-complete. CoRR Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini
2017	J	`jnl`	Maximizing the area of intersection of rectangles. CoRR David B. A. Epstein, Mike Paterson
2014	J	`jnl`	False-Name Manipulations in Weighted Voting Games. CoRR Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson
2014	A*	`conf`	Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. SODA Thomas Dueholm Hansen, Mike Paterson, Uri Zwick
2011	J	`jnl`	False-Name Manipulations in Weighted Voting Games. J. Artif. Intell. Res. Haris Aziz, Yoram Bachrach, Edith Elkind, Mike Paterson
2009	J	`jnl`	False name manipulations in weighted voting games: splitting, merging and annexation CoRR Haris Aziz, Mike Paterson
2009	—	`conf`	False name manipulations in weighted voting games: splitting, merging and annexation. AAMAS (1) Haris Aziz, Mike Paterson
2009	J	`jnl`	Maximum Overhang. Am. Math. Mon. Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
2009	J	`jnl`	Overhang. Am. Math. Mon. Mike Paterson, Uri Zwick
2009	C	`conf`	Power Indices in Spanning Connectivity Games. AAIM Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
2009	J	`jnl`	Spanning connectivity games CoRR Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
2009	J	`jnl`	The Multi-Commodity Source Location Problems and the Price of Greed. J. Graph Algorithms Appl. Hiro Ito, Mike Paterson, Kenya Sugihara
2009	—	`conf`	Wiretapping a Hidden Network. WINE Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
2009	J	`jnl`	Wiretapping a hidden network CoRR Haris Aziz, Oded Lachish, Mike Paterson, Rahul Savani
2008	J	`jnl`	A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM J. Comput. Marcin Jurdzinski, Mike Paterson, Uri Zwick
2008	J	`jnl`	Computing voting power in easy weighted voting games CoRR Haris Aziz, Mike Paterson
2008	A*	`conf`	Maximum overhang. SODA Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
2008	B	`conf`	Multi-commodity Source Location Problems and Price of Greed. WALCOM Hiro Ito, Mike Paterson, Kenya Sugihara
2008	—	`conf`	Polynomial-Time Construction of Linear Network Coding. ICALP (1) Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita
2007	—	`ed.`	Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers ESCAPE Bo Chen, Mike Paterson, Guochuan Zhang
2007	J	`jnl`	On counting homomorphisms to directed acyclic graphs. J. ACM Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson
2006	A*	`conf`	A deterministic subexponential algorithm for solving parity games. SODA Marcin Jurdzinski, Mike Paterson, Uri Zwick
2006	J	`jnl`	Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z LMS J. Comput. Math. Leslie Ann Goldberg, Markus Jalsenius, Russell Martin, Mike Paterson
2006	—	`conf`	On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson
2006	A*	`conf`	Overhang. SODA Mike Paterson, Uri Zwick
2005	J	`jnl`	On counting homomorphisms to directed acyclic graphs Electron. Colloquium Comput. Complex. Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson
2005	J	`jnl`	Strong Spatial Mixing with Fewer Colors for Lattice Graphs. SIAM J. Comput. Leslie Ann Goldberg, Russell A. Martin, Mike Paterson
2004	J	`jnl`	A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput. Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson
2004	B	`conf`	Analysis of Scheduling Algorithms for Proportionate Fairness. LATIN Mike Paterson
2004	J	`jnl`	Random sampling of 3-colorings in Z Random Struct. Algorithms Leslie Ann Goldberg, Russell A. Martin, Mike Paterson
2004	J	`jnl`	The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random. SIAM J. Comput. Leslie Ann Goldberg, Steven Kelk, Mike Paterson
2004	A*	`conf`	trong Spatial Mixing for Lattice Graphs with Fewer Colours. FOCS Leslie Ann Goldberg, Russell A. Martin, Mike Paterson
2003	J	`jnl`	A family of NFAs which need 2n- deterministic states. Theor. Comput. Sci. Kazuo Iwama, Akihiro Matsuura, Mike Paterson
2003	B	`conf`	A proportionate fair scheduling rule with good worst-case performance. SPAA Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson
2003	J	`jnl`	The computational complexity of two-state spin systems. Random Struct. Algorithms Leslie Ann Goldberg, Mark Jerrum, Mike Paterson
2002	J	`jnl`	Permutation Communication in All-Optical Rings. Parallel Process. Lett. Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto
2002	A*	`conf`	The complexity of choosing an H-colouring (nearly) uniformly at random. STOC Leslie Ann Goldberg, Steven Kelk, Mike Paterson
2001	J	`jnl`	Better Approximation Guarantees for Job-Shop Scheduling. SIAM J. Discret. Math. Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
2001	J	`jnl`	The Complexity of Gene Placement. J. Algorithms Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk
2000	A*	`conf`	A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. ICALP Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson
2000	B	`conf`	A Family of NFA's Which Need 2 MFCS Kazuo Iwama, Akihiro Matsuura, Mike Paterson
2000	A	`ed.`	Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings ESA Mike Paterson
2000	A*	`conf`	Communication complexity of document exchange. SODA Graham Cormode, Mike Paterson, Süleyman Cenk Sahinalp, Uzi Vishkin
2000	J	`jnl`	Contention resolution with constant expected delay. J. ACM Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, Aravind Srinivasan
2000	J	`jnl`	Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theor. Comput. Sci. Somasundaram Ravindran, Alan Gibbons, Mike Paterson
2000	A*	`conf`	Tight Size Bounds for Packet Headers in Narrow Meshes. ICALP Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson
1999	B	`ed.`	Combinatorial Pattern Matching, 10th Annual Symposium, CPM 99, Warwick University, UK, July 22-24, 1999, Proceedings CPM Maxime Crochemore, Mike Paterson
1999	A*	`conf`	Compact Grid Layouts of Multi-Level Networks. STOC S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel
1999	J	`jnl`	On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). SIAM J. Comput. Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup
1999	J	`jnl`	Optimal Layout of Edge-weighted Forests. Discret. Appl. Math. Michael J. Fischer, Mike Paterson
1999	A*	`conf`	The Complexity of Gene Placement. SODA Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk
1999	J	`jnl`	The chip in your wallet - The technology of security in smartcard chip manufacture. Inf. Secur. Tech. Rep. Mike Paterson
1998	J	`jnl`	Consistency of Natural Relations on Sets. Comb. Probab. Comput. Akira Maruoka, Mike Paterson, Hirotaka Koizumi
1998	B	`conf`	Layout of the Batcher Bitonic Sorter (Extended Abstract). SPAA Shimon Even, S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp
1998	A*	`conf`	On Approximating Rectangle Tiling and Packing. SODA Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
1998	B	`conf`	On permutation communications in all-optical rings. SIROCCO Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto
1997	A*	`conf`	Better Approximation Guarantees for Job-shop Scheduling. SODA Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk
1997	J	`jnl`	Lower Bounds for Monotone Span Programs. Comput. Complex. Amos Beimel, Anna Gál, Mike Paterson
1997	J	`jnl`	On Nearest-Neighbor Graphs. Discret. Comput. Geom. David Eppstein, Mike Paterson, F. Frances Yao
1997	B	`conf`	On Weak Circular Squares in Binary Words. CPM Aviezri S. Fraenkel, Jamie Simpson, Mike Paterson
1996	A*	`conf`	On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). SODA Richa Agarwala, Vineet Bafna, Martin Farach, Babu O. Narayanan, Mike Paterson, Mikkel Thorup
1996	A*	`conf`	On the Complexity of String Folding. ICALP Mike Paterson, Teresa M. Przytycka
1996	J	`jnl`	On the Complexity of String Folding. Discret. Appl. Math. Mike Paterson, Teresa M. Przytycka
1996	—	`conf`	Progress in Selection. SWAT Mike Paterson
1996	J	`jnl`	The Asymptotic Complexity of Merging Networks. J. ACM Peter Bro Miltersen, Mike Paterson, Jun Tarui
1996	J	`jnl`	The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. Uri Zwick, Mike Paterson
1995	A*	`conf`	Contention Resolution with Bounded Delay. FOCS Mike Paterson, Aravind Srinivasan
1995	—	`conf`	Looking for MUM and DAD: Text-Text Comparisons Do Help. FSTTCS Mike Paterson, Shlomit Tassa, Uri Zwick
1995	J	`jnl`	Lower Bounds for Monotone Span Programs Electron. Colloquium Comput. Complex. Amos Beimel, Anna Gál, Mike Paterson
1995	A*	`conf`	Lower Bounds for Monotone Span Programs. FOCS Amos Beimel, Anna Gál, Mike Paterson
1995	J	`jnl`	PI Comput. Complex. Alain P. Hiltgen, Mike Paterson
1995	J	`jnl`	The Complexity of Mean Payoff Games on Graphs Electron. Colloquium Comput. Complex. Uri Zwick, Mike Paterson
1995	Misc	`conf`	The Complexity of Mean Payoff Games. COCOON Uri Zwick, Mike Paterson
1995	J	`jnl`	Tighter Lower Bounds on the Exact Complexity of String Matching. SIAM J. Comput. Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
1995	J	`jnl`	Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. Random Struct. Algorithms Vlado Dancík, Mike Paterson
1994	J	`jnl`	David Michael Ritchie Park (1935-1990) in Memoriam. Theor. Comput. Sci. Mike Paterson
1994	J	`jnl`	Fishspear: A Priority Queue Algorithm. J. ACM Michael J. Fischer, Mike Paterson
1994	B	`conf`	Longest Common Subsequences. MFCS Mike Paterson, Vlado Dancík
1994	A	`conf`	Upper Bounds for the Expected Length of a Longest Common Subsequence of Two Binary Sequences. STACS Vlado Dancík, Mike Paterson
1993	J	`jnl`	A Short Proof of the Dilation of a Toroidal Mesh in a Path. Inf. Process. Lett. Mike Paterson, Heiko Schröder, Ondrej Sýkora, Imrich Vrto
1993	A	`conf`	Evolution of an Algorithm. ESA Mike Paterson
1993	J	`jnl`	Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication. Comput. Complex. Mike Paterson, Uri Zwick
1993	J	`jnl`	Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms Mike Paterson, Uri Zwick
1993	J	`jnl`	The Memory Game. Theor. Comput. Sci. Uri Zwick, Mike Paterson
1993	—	`conf`	Which Patterns are Hard to Find? ISTCS Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
1992	B	`conf`	Boolean Circuit Complexity. ISAAC Mike Paterson
1992	B	`conf`	Dense Edge-Disjoint Embedding of Binary Trees in the Mesh. SPAA Alan Gibbons, Mike Paterson
1992	A*	`conf`	On Nearest-Neighbor Graphs. ICALP Mike Paterson, F. Frances Yao
1992	J	`jnl`	Optimal Binary Space Partitions for Orthogonal Objects. J. Algorithms Mike Paterson, F. Frances Yao
1992	A*	`conf`	Shallow Multiplication Circuits and Wise Financial Investments STOC Mike Paterson, Uri Zwick
1992	A*	`conf`	The Asymptotic Complexity of Merging Networks FOCS Peter Bro Miltersen, Mike Paterson, Jun Tarui
1991	J	`jnl`	Planar Acyclic Computation Inf. Comput. William F. McColl, Mike Paterson, Brian H. Bowditch
1991	A*	`conf`	Shrinkage of de~Morgan formulae under restriction FOCS Mike Paterson, Uri Zwick
1991	B	`conf`	The MINSUMCUT Problem. WADS Josep Díaz, Alan Gibbons, Mike Paterson, Jacobo Torán
1991	J	`jnl`	The Set of Minimal Braids is co-NP-Complete. J. Algorithms Mike Paterson, Alexander A. Razborov
1990	A*	`ed.`	Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings ICALP Mike Paterson
1990	J	`jnl`	Computing Euclidean Maximum Spanning Trees. Algorithmica Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao
1990	J	`jnl`	Efficient Binary Space Partitions for Hidden-Surface Removal and Solid Modeling. Discret. Comput. Geom. Mike Paterson, F. Frances Yao
1990	A*	`conf`	Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions FOCS Mike Paterson, Nicholas Pippenger, Uri Zwick
1990	J	`jnl`	Improved Sorting Networks with O(log N) Depth. Algorithmica Mike Paterson
1990	A*	`conf`	Optimal Binary Space Partitions for Orthogonal Objects. SODA Mike Paterson, F. Frances Yao
1989	—	`conf`	Binary Partitions with Applications to Hidden Surface Removal and Solid Modelling. SCG Mike Paterson, F. Frances Yao
1989	J	`jnl`	Partitioning Space for Range Queries. SIAM J. Comput. F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, Mike Paterson
1988	—	`conf`	Computing Euclidean Maximum Spanning Trees. SCG Clyde L. Monma, Mike Paterson, Subhash Suri, F. Frances Yao
1988	J	`jnl`	Universal Chains and Wiring Layouts. SIAM J. Discret. Math. Mike Paterson
1987	J	`jnl`	The Planar Realization of Boolean Functions. Inf. Process. Lett. William F. McColl, Mike Paterson
1986	J	`jnl`	Nearly Optimal Hierarchies for Network and Formula Size. Acta Informatica Mike Paterson, Ingo Wegener
1986	J	`jnl`	Point Retrieval for Polygons. J. Algorithms Mike Paterson, F. Frances Yao
1985	A*	`conf`	Dynamic Monotone Priorities on Planar Sets (Extended Abstract) FOCS Michael J. Fischer, Mike Paterson
1985	J	`jnl`	Impossibility of Distributed Consensus with One Faulty Process J. ACM Michael J. Fischer, Nancy A. Lynch, Mike Paterson
1984	A*	`conf`	Fishspear: A Priority Queue Algorithm (Extended Abstract) FOCS Michael J. Fischer, Mike Paterson
1984	J	`jnl`	Undecidability of PDL with L={a^(2i)\|i>=0}. J. Comput. Syst. Sci. David Harel, Mike Paterson
1983	A*	`conf`	Impossibility of Distributed Consensus with One Faulty Process. PODS Michael J. Fischer, Nancy A. Lynch, Mike Paterson
1983	J	`jnl`	Storage Requirements for Fair Scheduling. Inf. Process. Lett. Michael J. Fischer, Mike Paterson
1982	J	`jnl`	Efficient Parallel Algorithms for Linear Recurrence Computation. Inf. Process. Lett. Albert G. Greenberg, Richard E. Ladner, Mike Paterson, Zvi Galil
1982	J	`jnl`	Omega(n log n) Lower Bounds on Length of Boolean Formulas. SIAM J. Comput. Michael J. Fischer, Albert R. Meyer, Mike Paterson
1981	A*	`conf`	Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract) STOC Mike Paterson, Walter L. Ruzzo, Lawrence Snyder
1981	J	`jnl`	Optimal Packing and Covering in the Plane are NP-Complete. Inf. Process. Lett. Robert J. Fowler, Mike Paterson, Steven L. Tanimoto
1981	J	`jnl`	Propositional Dynamic Logic is Weaker without Tests. Theor. Comput. Sci. Francine Berman, Mike Paterson
1980	J	`jnl`	A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. William J. Masek, Mike Paterson
1980	J	`jnl`	Asymtotically Optimal Circuit for a Storage Access Function. IEEE Trans. Computers Peter Klein, Mike Paterson
1980	A*	`conf`	Optimal Tree Layout (Preliminary Version) STOC Michael J. Fischer, Mike Paterson
1980	J	`jnl`	Selection and Sorting with Limited Storage. Theor. Comput. Sci. J. Ian Munro, Mike Paterson
1979	—	`conf`	The linear postman: a message-forwarding algorithm using sequential storage. Algorithms in Modern Mathematics and Computer Science Mike Paterson
1978	J	`jnl`	Linear Unification. J. Comput. Syst. Sci. Mike Paterson, Mark N. Wegman
1978	A*	`conf`	Selection and Sorting with Limited Storage FOCS J. Ian Munro, Mike Paterson
1977	—	`conf`	New bounds on formula size. Theoretical Computer Science Mike Paterson
1977	J	`jnl`	The Depth of All Boolean Functions. SIAM J. Comput. William F. McColl, Mike Paterson
1976	J	`jnl`	Circuit Size is Nonlinear in Depth. Theor. Comput. Sci. Mike Paterson, Leslie G. Valiant
1976	J	`jnl`	Finding the Median. J. Comput. Syst. Sci. Arnold Schönhage, Mike Paterson, Nicholas Pippenger
1976	A*	`conf`	Linear Unification STOC Mike Paterson, Mark N. Wegman
1975	J	`jnl`	Complexity of Monotone Networks for Boolean Matrix Product. Theor. Comput. Sci. Mike Paterson
1975	J	`jnl`	Deterministic One-Counter Automata. J. Comput. Syst. Sci. Leslie G. Valiant, Mike Paterson
1975	A*	`conf`	Lower Bounds on the Size of Boolean Formulas: Preliminary Report STOC Michael J. Fischer, Albert R. Meyer, Mike Paterson
1974	A*	`conf`	Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract) STOC Ronald V. Book, Maurice Nivat, Mike Paterson
1974	J	`jnl`	Reversal-Bounded Acceptors and Intersections of Linear Languages. SIAM J. Comput. Ronald V. Book, Maurice Nivat, Mike Paterson
1973	J	`jnl`	A note on disjunctive form tautologies. SIGACT News M. Bauer, D. Brand, Michael J. Fischer, Albert R. Meyer, Mike Paterson
1973	—	`conf`	Deterministic one-counter automata. Automatentheorie und Formale Sprachen Leslie G. Valiant, Mike Paterson
1973	J	`jnl`	On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. Mike Paterson, Larry J. Stockmeyer
1973	J	`jnl`	Optimal Algorithms for Parallel Polynomial Evaluation. J. Comput. Syst. Sci. J. Ian Munro, Mike Paterson
1972	—	`conf`	Decision problems in computational models. International Sympoisum on Theoretical Programming Mike Paterson
1972	J	`jnl`	Tape Bounds for Time-Bounded Turing Machines. J. Comput. Syst. Sci. Mike Paterson
1971	—	`conf`	Bounds on the Evaluation Time for Rational Polynomials SWAT Mike Paterson, Larry J. Stockmeyer
1971	—	`conf`	Optimal Algorithms for Parallel Polynomial Evaluation SWAT J. Ian Munro, Mike Paterson
1970	J	`jnl`	On Formalised Computer Programs. J. Comput. Syst. Sci. David C. Luckham, David Michael Ritchie Park, Mike Paterson
1970	—	`conf`	Tape-Bounds for Time-Bounded Turing Machines SWAT Mike Paterson