Peter Winkler

Orcid: 0000-0002-1259-3574

  • Dartmouth College, Hanover, USA

According to our database1, Peter Winkler authored at least 112 papers between 1980 and 2022.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:



An Ancient Combinatorial Problem.
Am. Math. Mon., 2022

Permutations with fixed pattern densities.
Random Struct. Algorithms, 2020

Mixing of Permutations by Biased Transpositions.
Theory Comput. Syst., 2019

Abelian Logic Gates.
Comb. Probab. Comput., 2019

The Sleeping Beauty Controversy.
Am. Math. Mon., 2017

Firefighting on Geometric Graphs with Density Bounds.
Ars Comb., 2017

Mixing of Permutations by Biased Transposition.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Cop vs. Gambler.
Discret. Math., 2016

Firefighting on a random geometric graph.
Random Struct. Algorithms, 2015

Performance evaluation of fragmented structures: A theoretical study.
Perform. Evaluation, 2014

Mixing Times and Moving Targets.
Comb. Probab. Comput., 2014

New Bounds for Edge-Cover by Random Walk.
Comb. Probab. Comput., 2014

Capturing the Drunk Robber on a Graph.
Electron. J. Comb., 2014

Puzzled: Paths and Matchings.
Commun. ACM, 2014

Puzzled: A Sort, of Sorts.
Commun. ACM, 2014

Puzzled: Lowest Number Wins.
Commun. ACM, 2014

Proceedings of the Innovations in Theoretical Computer Science, 2014

Cops vs. Gambler.
CoRR, 2013

Puzzled: Coin flipping.
Commun. ACM, 2013

Puzzled answers.
Commun. ACM, 2013

Impeding forgers at photo inception.
Proceedings of the Media Watermarking, 2013

On the Isolation of a Common Secret.
Proceedings of the Mathematics of Paul Erdős II, 2013

Two-Color Babylon.
Integers, 2012

Review: Famous Puzzles of Great Mathematicians. American Mathematical Society, Providence, RI, 2009, xviii + 325 pp., ISBN 978-0-8218-4814-2, $36. by Miodrag S. Petkovič.
Am. Math. Mon., 2011

Building Graphs from Colored Trees.
Electron. J. Comb., 2010

Commun. ACM, 2010

Breaking chocolate bars.
Commun. ACM, 2010

Maximum Overhang.
Am. Math. Mon., 2009

Branched Polymers.
Am. Math. Mon., 2009

Submodular Percolation.
SIAM J. Discret. Math., 2009

Puzzled - Covering the plane.
Commun. ACM, 2009

Puzzled - Solutions and sources.
Commun. ACM, 2009

Puzzled - Probability and intuition.
Commun. ACM, 2009

Puzzled - Understanding relationships among numbers.
Commun. ACM, 2009

Puzzled - Will my algorithm terminate?
Commun. ACM, 2009

Sorting by placement and shift.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

On a Form of Coordinate Percolation.
Comb. Probab. Comput., 2008

Puzzled: Circular food.
Commun. ACM, 2008

Luck vs. Skill.
Proceedings of the Combinatorial and Algorithmic Aspects of Networking, 4th Workshop, 2007

A Solidification Phenomenon in Random Packings.
SIAM J. Math. Anal., 2006

Dominating sets in k-majority tournaments.
J. Comb. Theory B, 2006

Data Synchronization Methods Based on ShuffleNet and Hypercube for Networked Information Systems.
Proceedings of the INFOCOM 2006. 25th IEEE International Conference on Computer Communications, 2006

Mixing Points on a Circle.
Proceedings of the Approximation, 2005

Mixing Points on an Interval.
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, 2005

Counting Eulerian Circuits is #P-Complete.
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, 2005

Building uniformly random subtrees.
Random Struct. Algorithms, 2004

A second threshold for the hard-core model on a Bethe lattice.
Random Struct. Algorithms, 2004

Note on Counting Eulerian Circuits
CoRR, 2004

How random is the human genome?
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On Playing Golf with Two Balls.
SIAM J. Discret. Math., 2003

Wavelength assignment and generalized interval graph coloring.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Packing rectangles in a strip.
Acta Informatica, 2002

Clustering and Server Selection using Passive Monitoring.
Proceedings of the Proceedings IEEE INFOCOM 2002, 2002

Wide-Sense Nonblocking WDM Cross-Connects.
Proceedings of the Algorithms, 2002

Rapid Mixing.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Optimal Carrier Sharing in Wireless TDMA.
J. Interconnect. Networks, 2001

Optimality and Greed in Dynamic Allocation.
J. Algorithms, 2001

Universal configurations in light-flipping games.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Graph Homomorphisms and Long Range Action.
Proceedings of the Graphs, 2001

Dependent percolation and colliding random walks.
Random Struct. Algorithms, 2000

Gibbs Measures and Dismantlable Graphs.
J. Comb. Theory B, 2000

Optimal linear arrangement of a rectangular grid.
Discret. Math., 2000

Average-Case Analysis of Retangle Packings.
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

Erratum: Mean distance and minimum degree.
J. Graph Theory, 1999

Graph Homomorphisms and Phase Transitions.
J. Comb. Theory B, 1999

The Ring Loading Problem.
SIAM J. Discret. Math., 1998

Ramsey Theory and Sequences of Random Variables.
Comb. Probab. Comput., 1998

Reversal of Markov Chains and the Forget Time.
Comb. Probab. Comput., 1998

Ring Routing and Wavelength Translation.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Mean distance and minimum degree.
J. Graph Theory, 1997

Computing with Snakes in Directed Networks of Automata.
J. Algorithms, 1997

Mixing times.
Proceedings of the Microsurveys in Discrete Probability, 1997

Multiple cover time.
Random Struct. Algorithms, 1996

Shuffling Biological Sequences.
Discret. Appl. Math., 1996

Comparing Information Without Leaking It.
Commun. ACM, 1996

On the Number of Eulerian Orientations of a Graph.
Algorithmica, 1996

On the Size of a Random Maximal Graph.
Random Struct. Algorithms, 1995

Monotone Gray Codes and the Middle Levels Problem.
J. Comb. Theory A, 1995

Exact Mixing in an Unknown Markov Chain.
Electron. J. Comb., 1995

Efficient stopping rules for Markov chains.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

A Key Escrow System with Warrant Bounds.
Proceedings of the Advances in Cryptology, 1995

Bounding the Vertex Cover Number of a Hypergraph.
Comb., 1994

Collisions Among Random Walks on a Graph.
SIAM J. Discret. Math., 1993

A note on the last new vertex visited by a random walk.
J. Graph Theory, 1993

Fast Information Sharing in a Complete Network.
Discret. Appl. Math., 1993

Three Thresholds for a Liar.
Comb. Probab. Comput., 1992

Target Shooting with Programmed Random Variables
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On the Number of Eularian Orientations of a Graph.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

On Playing "Twenty Questions" with a Liar.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

The number of t-wise balance designs.
Comb., 1991

Counting Linear Extensions is #P-Complete
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

On a Random Walk Problem Arising in Self-Stabilizing Token Management.
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Maximal Chains and Antichains in Boolean Lattices.
SIAM J. Discret. Math., 1990

Maximum itting Time for Random Walks on Graphs.
Random Struct. Algorithms, 1990

Extremal cover times for random walks on trees.
J. Graph Theory, 1990

Mean distance in a tree.
Discret. Appl. Math., 1990

Computing with Snakes in Directed Networks of Automata (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Ramsey-Type Theorem for Orderings of a Graph.
SIAM J. Discret. Math., 1989

The Complexity of Metric Realization.
SIAM J. Discret. Math., 1988

Every connected graph is a query graph.
J. Graph Theory, 1987

Factoring a Graph in Polynomial Time.
Eur. J. Comb., 1987

Collapse of the Metric Hierarchy for Bipartite Graphs.
Eur. J. Comb., 1986

On the addressing problem for directed graphs.
Graphs Comb., 1985

Isometric embedding in products of complete graphs.
Discret. Appl. Math., 1984

Existence of graphs with a given set of <i>r</i>-neighborhoods.
J. Comb. Theory B, 1983

Vertex-to-vertex pursuit in a graph.
Discret. Math., 1983

On families of finite sets with bounds on unions and intersections.
Discret. Math., 1983

The Advent of Cryptology in the Game of Bridge.
Cryptologia, 1983

Proof of the squashed cube conjecture.
Comb., 1983

On Computability of the Mean Deviation.
Inf. Process. Lett., 1982

Average height in a partially ordered set.
Discret. Math., 1982

On connectivity of triangulations of manifolds.
Discret. Math., 1980