A branched polymer of order n in R D —or just “polymer ” for short—is a connected set of n labeled unit spheres with nonoverlapping interiors. We will assume that the sphere labeled 1 is...
Sorting by Placement and Shift (2009)
In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to...
A Wordy Digression: The Game of Hipe (2009)
In Mathematical Mind-Benders, Peter Winkler. Wellesley, MA: A.K. Peters, 2007. Reprinted by permission of A.K. Peters, Ltd.
Vladimir Janković, Ivan Matić, Nikola Petrović, Ivan Matić, Peter Winkler, Vladimir Janković, ...
York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer...
Graham R. Brightwell, Peter Winkler
Abstract Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete...
Packing Rectangles in a Strip 1 (2009)
Peter Winkler, Bell Labs, Lucent Technologies
Abstract Rectangles with dimensions independently chosen from a uniform distribution on [0,1] are packed on-line into a unit-width strip under a constraint like that of the Tetris TM game: rectangles...
Puzzled solutions and sources (2009)
Solutions to three brain teasers concerning relationships among numbers are presented.
Puzzled solutions and sources (2009)
Solutions to three brain teasers concerning relationships among numbers are presented.
A branched polymer is a connected configuration of non-overlapping unit balls in space. Building on and from the work of Brydges and Imbrie, we give an elementary calculation of the volume of the...
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...
Solutions to puzzles concerning circular food shapes presented in a previous issue are presented.
Sorting by Placement and Shift (2008)
Elizalde, Sergi, Winkler, Peter
In sorting situations where the final destination of each item is known, it is natural to repeatedly choose items and place them where they belong, allowing the intervening items to shift by one to...
Shimon Even, Ami Litman, Peter Winkler
We consider directed, strongly connected networks of identical finite-state automata, of bounded in- and out-degree but unknown topology and unbounded size n. Protocols which are quadratic or linear...
David J. Houck, Kin K. Leung, Peter Winkler
Abstract – In contrast to a typical single source of data updates in Internet applications, data files in a networked information system are often distributed, replicated, accessed and updated by...
Abstract Chapter 18 On the Number of Eulerian Orientations of a Graph (2008)
We give efficient randomized schemes to sample and approximately count Eulerian orientations of any Eulerian graph. Eulerian orientations are natural flow-like structures, and Welsh has pointed out...
On a Form of Coordinate Percolation (2008)
Elizabeth R. Moseman, Peter Winkler
Let ai, bi, i = 0, 1, 2,... be drawn uniformly and independently from the unit interval, and let t be a fixed real number. Let a site (i, j) ∈ N 2 be open if ai + bj ≤ t, and closed otherwise. We...
y 1 \Lights Out " and \Orbix" (2007)
Universal Con, Yevgeniy Dodis, Peter Winkler
The following is a popular hand-held electronic game by Tiger Electronics, called \Lights Out". This game is played on a 5 5 grid of buttons which also have lights in them. By pressing a...
Brenda J. Latka, Peter Winkler, Discussions Stephen Greenfield
Tournament embedding is an order relation on the class of finite tournaments. An antichain is a set of finite tournaments that are pairwise incomparable in this ordering. We say an antichain A can be...
Ronald Fagin, Moni Naor, Peter Winkler
How can two people determine without revealing anything else to each other whether they possess the same information— in case they do not? There are surprisingly simple solutions.
SIAM J. DISCRETE MATH. c (2007)
Alexander Schrijver, Paul Seymour, Peter Winkler
Abstract. The following problem arose in the planning of optical communications networks which use bidirectional SONET rings. Tra#c demands d i,j are given for each pair of nodes in an n-node ring;...
Reversal of Markov Chains and the Forget Time Laszlo Lovasz (2007)
We study three quantities that can each be viewed as the time needed for a finite irreducible Markov chain to "forget " where it started. One of these is the mixing time, the...
1 Packing Random Intervals (2007)
E. G. Coffman, Bjorn Poonen, Peter Winkler
Abstract. Let n random intervals I 1; : : : ; I n be chosen by selecting endpoints independently from the uniform distribution on [0; 1]. A packing is a pairwise disjoint subset of the intervals; its...
Kenyon, Richard, Winkler, Peter
Building on and from the work of Brydges and Imbrie, we give an elementary calculation of the volume of the space of branched polymers of order $n$ in the plane and in 3-space. Our development...
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...
Level density of the Hénon-Heiles system above the critical barrier energy (2006)
Brack, Matthias, Kaidel, Jörg, Winkler, Peter, Fedotkin, Sergey
We discuss the coarse-grained level density of the Hénon-Heiles system above the barrier energy, where the system is nearly chaotic. We use periodic orbit theory to approximate its oscillating part...
Steinbrecht, Wolfgang, Haßler, Birgit, Brühl, Christoph, Dameris, Martin, Giorgetta, Marco, Grewe, Volker, ...
We report results from a multiple linear regression analysis of long-term total ozone observations (1979 to 2000, by TOMS/SBUV), of temperature reanalyses (1958 to 2000, NCEP), and of two...
Winkler, Peter, Lugauer, Matthias, Reitebuch, Oliver
„Alpines Pumpen“ ist ein regionales Zirkulationsphänomen, das sich tagsüber zwischen Gebirge und Vorland bei hoher Sonneneinstrahlung und schwachen Druckgradienten ausbildet. Die Luft im...
A Solidification Phenomenon in Random Packings (2005)
Bowen, Lewis, Lyons, Russell, Radin, Charles, Winkler, Peter
We prove that uniformly random packings of copies of a certain simply-connected figure in the plane exhibit global connectedness at all sufficiently high densities, but not at low densities.
Dominating sets in k-majority tournaments (2004)
Alon, Noga, Brightwell, Graham, Kierstead, H. A., Kostochka, A. V., Winkler, Peter
A k-majority tournament T on a finite vertex set V is defined by a set of 2k − 1 linear orderings of V , with u ! v if and only if u lies above v in at least k of the orders. Motivated in part by...
Note on counting Eulerian circuits (2004)
Brightwell, Graham, Winkler, Peter
We show that the problem of counting the number of Eulerian circuits in an undirected graph is complete for the class #P.
Periodic orbit theory for the continuum of general mixed-dynamical systems (2004)
Kaidel, Jörg, Winkler, Peter, Brack, Matthias
We investigate the resonance spectrum of the H\\\'enon-Heiles potential up to twice the barrier energy. The quantum spectrum is obtained by the method of complex coordinate rotation. We use periodic...
A second threshold for the hard-core model on a Bethe lattice (2004)
Graham R. Brightwell, Houghton St, Peter Winkler
We determine the approximate value of a critical activity for the hard-core model on the Bethe lattice, which determines whether the unique simple invariant Gibbs measure is extremal. This...
On the Economics of Multicasting (2004)
Yuval Shavitt Shavitt, Peter Winkler
A supplier of multicast information services will often be faced with the following problem: Broadcasting to the whole customer base (including non-paying customers) is cheaper than multicasting only...
On the Economics of Multicasting (2004)
Yuval Shavitt, Peter Winkler, Avishai Wool
this paper we investigate, in a more general setting, the economic consequences that such an approach brings
Dominating Sets in k-Majority Tournaments (2004)
Noga Alon, Graham Brightwell, H. A. Kierstead, A. V. Kostochka, Peter Winkler
A k-majority tournament T on a finite vertex set V is defined by a set of 2k − 1 linear orderings of V, with u → v if and only if u lies above v in at least k of the orders. Motivated in part by...
www.elsevier.com/locate/jctb Dominating sets in k-majority tournaments
Brightwell, Graham R., Winkler, Peter
Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete mathematician...
A second threshold for the hard-core model on a Bethe lattice (2003)
Brightwell, Graham, Winkler, Peter
We determine the approximate value of a critical activity for the hard-core model on the Bethe lattice, which determines whether the unique simple invariant Gibbs measure is extremal. This...
Wavelength assignment and generalized interval graph coloring (2003)
Abstract In this paper we study wavelength assignment on an optical linesystem without wavelength conversion. Consider a set of undirected demands along the line. Each demand is carried on a...
Random colorings of a cayley tree (2002)
Brightwell, Graham, Winkler, Peter
This volume is a collection of survey papers in combinatorics that have grown out of lectures given in the workshop on Probabilistic Combinatorics at the Paul Erdös Summer Research Center in...
Clustering and Server Selection Using Passive Monitoring (2002)
Matthew Andrews, Bruce Shepherd, Aravind Srinivasan, Peter Winkler, Francis Zane
Abstract — We consider the problem of client assignment in a distributed system of content servers. We present a system called Webmapper for clustering IP addresses and assigning each cluster to an...
Random colorings of a Cayley tree (2002)
Graham R. Brightwell, Houghton St, Peter Winkler
Probability measures on the space of proper colorings of a Cayley tree #that is, an in#nite regular connected graph with no cycles # are of interest not only in combinatorics but also in statistical...
Nonmonotonic behavior in hard-core and Widom-Rowlinson models (1999)
Graham R. Brightwell, Olle Haggstrom, Peter Winkler
We give two examples of nonmonotonic behavior in symmetric systems, exhibiting more than one critical point at which spontaneous symmetry-breaking appears or disappears. The two systems are the...
Gibbs Measures and Dismantlable Graphs (1999)
Graham R. Brightwell, Houghton St, Peter Winkler
We model physical systems with "hard constraints" by the space Hom(G;H) of homomorphisms from a locally finite graph G to a fixed finite constraint graph H . Two homomorphisms are deemed to...
theory and sequences of random variables (1998)
William T. Trotter, Peter Winkler
We consider probability spaces which contain a family {EA: A ⊆{1,2,...,n}, |A | = k} of events indexed by the k-element subsets of {1, 2,...,n}. A pair (A, B) of k-element subsets of {1, 2,...,n}...
Ring routing and wavelength translation (1998)
Let G be the digraph consisting of two oppositely-directed rings on the same set of n nodes. We provide a polynomial-time algorithm which, given a list of demands---each requiring a path from a...
Abstract. The critical issue in the complexity of Markov chain sampling techniques has been "mixing time", the number of steps of the chain needed to reach its stationary...
Ring Routing and Wavelength Translation (1998)
Let G be the digraph consisting of two oppositely-directed rings on the same set of n nodes. We provide a polynomialtime algorithm which, given a list of demands---each requiring a path from a...
. The critical issue in the complexity of Markov chain sampling techniques has been "mixing time", the number of steps of the chain needed to reach its stationary distribution. It turns out...
Nonmonotonic behavior in hard-core and Widom-Rowlinson models (1998)
Graham Brightwell, Olle Häggström, Peter Winkler
We give two examples of nonmonotonic behavior in symmetric systems, exhibiting more than one critical point at which spontaneous symmetry-breaking appears or disappears. The two systems are the...
Graph Homomorphisms and Phase Transitions (1997)
Graham R. Brightwell, Houghton St, Peter Winkler
We model physical systems with "hard constraints" by the space Hom(G;H) of homomorphisms from a locally finite graph G to a fixed finite constraint graph H. For any assignment of positive...
Typescript.
Reversal of Markov Chains and the Forget Time (1996)
We study three quantities that can each be viewed as the time needed for a finite irreducible Markov chain to "forget" where it started. One of these is the mixing time, the minimum mean...
Ramsey Theory And Sequences Of Random Variables (1996)
William T. Trotter, Peter Winkler
. We consider probability spaces which contain a family fEA : A ` f1; 2; : : : ; ng; jAj = kg of events indexed by the k--element subsets of f1; 2; : : : ; ng. A pair (A; B) of k--element subsets of...
Peter Winkler, David Zuckerman
Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within...
Comparing Information Without Leaking It (1996)
Ronald Fagin, Moni Naor, Peter Winkler
We consider simple means by which two people may determine whether they possess the same information, without revealing anything else to each other in case that they do not. Incumbent of the Morris...
Reversal of Markov Chains and the Forget Time (1996)
We study three quantities that can each be viewed as the time needed for a finite irreducible Markov chain to "forget" where it started. One of these is the mixing time, the minimum mean...
Peter Winkler, David Zuckerman
Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within...
Exact mixing in an unknown markov chain (1995)
We give a simple stopping rule which will stop an unknown, irreducible n-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected...
Exact mixing in an unknown markov chain (1995)
We give a simple stopping rule which will stop an unknown, irreducible n-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected...
Target Shooting with Programmed Random Variables (1995)
Graham Brightwell, Teun Ott, Peter Winkler
. Let X1 ; : : : ; Xn be pairwise independent random variables of known (but not necessarily identical) distribution; we wish to select a subset of these whose sum will be as close as possible to...
Monotone Gray Codes and the Middle Levels Problem (1995)
Peter Winkler, Carla Savage, Carla D. Savage
An n-bit binary Gray code is an enumeration of all n-bit binary strings so that successive elements differ in exactly one bit position; equivalently, a hamilton path in the Hasse diagram of B n (the...
A Key Escrow System with Warrant Bounds (1995)
Arjen K. Lenstra, Peter Winkler, Yacov Yacobi
. We propose a key escrow system that permits warrants for the interception and decryption of communications for arbitrary time periods, and with either one or two communicating parties specified as...
Exact Mixing in an Unknown Markov Chain (1995)
We give a simple stopping rule which will stop an unknown, irreducible n-state Markov chain at a state whose probability distribution is exactly the stationary distribution of the chain. The expected...
Monotone Gray Codes and the Middle Levels Problem (1995)
Peter Winkler, Carla D. Savage, Carla D. Savage
An n-bit binary Gray code is an enumeration of all n-bit binary strings so that successive elements differ in exactly one bit position; equivalently, a hamilton path in the Hasse diagram of B n (the...
Efficient Stopping Rules for Markov Chains (1995)
) L' aszl' o Lov' asz Dept. of Computer Science, Yale University, New Haven CT 06510; lovasz@cs.yale.edu Peter Winkler AT&T Bell Laboratories 2D-147, Murray Hill NJ 07974;...
Mixing of Random Walks and Other Diffusions on a Graph (1995)
We survey results on two diffusion processes on graphs: random walks and chip-firing (closely related to the "abelian sandpile" or "avalanche" model of self-organized criticality...
The Spanning Tree Enumeration Problem for Digraphs (1995)
Nathaniel Dean, A. K. Kelmans, Keh-wei Lih, William A. Massey, Peter Winkler
Counting spanning trees is a fundamental problem in enumerative combinatorics. The conventional approach uses determinants, and explicit formulas have been found for several families of graphs,...
Efficient Stopping Rules for Markov Chains (Extended Abstract) (1995)
) L' aszl' o Lov' asz Dept. of Computer Science, Yale University, New Haven CT 06510; lovasz@cs.yale.edu Peter Winkler AT&T Bell Laboratories 2D-147, Murray Hill NJ 07974;...
Paraphonetische Formtypen : sozial-strukturelle Reglements in Sprechäusserungen / (1994)
Halle, Universiẗat, Habil.-Schr., 1996.
Fast Information Sharing in a Complete Network (1993)
: We consider the problem of complete information dissemination among n autonomous processors in a fully connected distributed system. Initially, each processor possesses information not held by any...
Collisions among Random Walks on a Graph (1993)
Don Coppersmith, Prasad Tetali, Peter Winkler
A token located at some vertex v of a connected, undirected graph G on n vertices is said to be taking a "random walk" on G if, whenever it is instructed to move, it moves with equal...
On Playing "Twenty Questions" with a Liar (1992)
Aditi Dhagat, Peter Gács, Peter Winkler
We consider a version of the game "Twenty Questions" played on the set f0; \Delta \Delta \Delta ; N \Gamma 1g where the player giving answers may lie in her answers. The questioner is...
Three Thresholds for a Liar (1992)
Joel Spencer, Peter Winkler, South St
Motivated by the problem of making correct computations from partly false information, we study a corruption of the classic game "Twenty Questions" in which the player who answers the...
On playing “twenty questions” with a liar (1992)
Aditi Dhagat, Peter Winkler, Bellcore L, Peter Gács
We consider a version of the game “Twenty Questions ” played on the set {0, · · · , N − 1} where the player giving answers may lie in her answers. The questioner is allowed Q questions and...
Computing with Snakes in Directed Networks of Automata (1990)
Shimon Even, Ami Litman, Peter Winkler
We consider unidirectional, strongly connected networks of identical finite-state automata, of bounded in- and out-degree but unknown topology and unbounded size n. Protocols which are quadratic or...
Dresden, Techn. Univ., Diss. B, 1986 (Nicht für den Austausch).
Kurzfassung in: Dtsch. Med. Wschr. Jg. 104. 1979, Nr. 37, S. 1301 - 1306 u.d.T.: Winkler, P.: Die Bedeutung der Anamnese für die Diagnostik entzündlich-rheumatischer Erkrankungen
Gerhard, Lutz., Igney, Diethart., Winkler, Peter.
Dresden, Techn. Univ., Fak. für Maschinenwesen, Diss., 1977. (Nicht f. d. Austausch.).
Thesis (doctoral)--Rheinisch-Westfälische Technische Hochschule Aachen, 1975.
Ingestionsunfälle mit Natriumfluoridtabletten. (1973)
Diss. med. Zürich 1973. (KA).
Halle, Univ., Philos. Fak., Diss. A, 1971. (Nicht f. d. Austausch.).
Einfluss der Hexadekapolwechselwirkung auf die Coulombanregung deformieter Atomkerne. (1969)
Erlangen-Nürnberg, Naturwiss. F., Diss. v. 27. Nov. 1969.
Thesis (doctoral)--Technische Hochschule Carolo-Wilhelmina zu Braunschweig, 1969.
Untersuchungen zu den niederenergetischen Niveauschemata von 110Ag und 128J. (1967)
Dresden, T. U., F. f. Math. u. Naturwiss., Diss. v. 12. Okt. 1967 (Nicht f. d. Aust.).
Puzzled: Will My Algorithm Terminate? (0000)
Welcome to three new challenging mathematical puzzles. Solutions to the first two will be published next month; the third is as yet unsolved. In them all, I concentrate on algorithm termination,...
On the Economics of Multicasting
Yuval Shavitt, Peter Winkler, Avishai Wool
A supplier of multicast information services will often be faced with the following problem: Broadcasting to the whole customer base (including non-paying customers) is cheaper than multicasting only...
The rising trends both in drug addiction and crime rates are of major public concern in Germany. Surprisingly, the economic theory of crime seems to ignore the drugs—crime nexus, whereas the...
Mixing Times for Uniformly Ergodic Markov Chains
David Aldous, László Lovász, Peter Winkler
Consider the class of discrete time, general state space Markov chains which satisfy a "uniform ergodicity under sampling" condition. There are many ways to quantify the notion of...
Puzzled: Will My Algorithm Terminate?
Welcome to three new challenging mathematical puzzles. Solutions to the first two will be published next month; the third is as yet unsolved. In them all, I concentrate on algorithm termination,...