Peter Winkler - Publications

    Peter Winkler - Publications

  1. Model-completeness and Skolem expansions, P. Winkler, Interactions between Model Theory and Algebra: A Memorial Tribute to Abraham Robinson, D. Saracino and V. Weispfenning (editors), Springer-Verlag, Berlin, Lecture Notes in Mathematics Vol. 498 (1975), pp. 408-463.
  2. Computational characterization of abelian groups, P. Winkler, The Kleene Symposium (Madison, WI, June 1978), J. Barwise, H.J. Keisler and K. Kunen (editors), North-Holland, Amsterdam, 1980, pp. 423-428.
  3. On connectivity of triangulations of manifolds, P. Winkler, Discrete Math. 32 (1980), pp. 93-94.
  4. Classification of algebraic structures by work space, P. Winkler, Algebra Universalis 11 (1980), pp. 320-333.
  5. Graphic characterization of k-trees, P. Winkler, Congressus Numerantium 37 (1981), pp. 349-357.
  6. Degree sets of k-trees: small k, R.A. Duke and P. Winkler, Israel J. Math. 40 (1981), pp. 296-306.
  7. Average height in a partially ordered set, P. Winkler, Discrete Math 39 (1982), pp. 337-341.
  8. On computability of the mean deviation, P. Winkler, Information Processing Letters 15 (1982), pp. 36-38.
  9. Minimizing setups in cycle-free ordered sets, D. Duffus, I. Rival and P. Winkler, Proc. Amer. Math. Soc. 85 (1982), pp. 509-513.
  10. A simple Venn diagram of five triangles (note), B. Grunbaum and P. Winkler, Math. Magazine 55:5 (1982), page 311.
  11. Realizability of almost all degree sets by k-trees, R.A. Duke and P. Winkler, Congressus Numerantium 35 (1982), pp. 261-274.
  12. Vertex-to-vertex pursuit in a graph, R. Nowakowski and P. Winkler, Discrete Math. 43 (1983), pp. 235-239.
  13. Correlation among partial orders, P. Winkler, SIAM J. on Algebraic and Discrete Methods 4:1 (1983), pp. 1-7.
  14. On families of finite sets with bounds on unions and intersections, C. Bang, H. Sharp Jr. and P. Winkler, Discrete Math. 45 (1983), pp. 123-126.
  15. Degree sets of k-trees: small degrees, R.A. Duke and P. Winkler, Utilitas Mathematica 23 (1983), pp. 177-200.
  16. Existence of graphs with a given set of r-neighborhoods, P. Winkler, J. Combinatorial Theory (B) 34:2 (1983), pp. 165-176.
  17. Proof of the squashed cube conjecture, P. Winkler, Combinatorica 3:1 (1983), pp. 135-139.
  18. Polynomial hyperforms, P. Winkler, Algebra Universalis 17 (1983), pp. 101-109.
  19. Isometric embedding in products of complete graphs, P. Winkler, Discrete Applied Math. 7 (1984), pp. 221-225.
  20. On coverings of a finite set: depth and subcovers, P. Winkler, C. Bang and H. Sharp Jr., Periodica Math. Hungarica 51:1 (1984), pp. 51-60.
  21. Isometric embeddings of graphs, R.L. Graham and P. Winkler, Proc. Natl. Acad. Sci. USA 81 (1984), pp. 7259-7260.
  22. Venn diagrams: some observations and an open problem, P. Winkler, Congressus Numerantium 45 (1984), pp. 267-274.
  23. On the addressing problem for directed graphs, F.R.K. Chung, R.L. Graham and P. Winkler, Graphs and Combinatorics 1:1 (1985), pp. 41-50.
  24. Random orders, P. Winkler, ORDER 1 (1985), pp. 317-331.
  25. On isometric embeddings of graphs, R.L. Graham and P. Winkler, Trans. Amer. Math. Soc. 288:2 (1985), pp. 527-536.
  26. On graphs which are metric spaces of negative type, P. Winkler, Graph Theory and its Applications to Algorithms and Computer Science, Y. Alavi (editor), John Wiley & Sons, New York, 1985, pp. 801-810.
  27. Connectedness and diameter for random orders of fixed dimension, P. Winkler, ORDER 2 (1985), pp. 165-171.
  28. Comparability invariance of the fixed point property, B. Dreesen, W. Poguntke and P. Winkler, ORDER 2 (1985), pp. 269-274.
  29. Collapse of the metric hierarchy for bipartite graphs, R.L. Roth and P. Winkler, European J. Combinatorics 7 (1986), pp. 371-375.
  30. Correlation and order, P. Winkler, Contemporary Mathematics 57 (1986), pp. 151-174.
  31. On the regular part of varieties of algebras, E. Graczynska, D. Kelly and P. Winkler, Algebra Universalis 23 (1986), pp. 77-84.
  32. Mean distance and the four-thirds conjecture, P. Winkler, Congressus Numerantium 54 (1986), pp. 63-72.
  33. Every connected graph is a query graph, P. Winkler, J. Graph Theory 11:2 (1987), pp. 231-234.
  34. Factoring a graph in polynomial time, P. Winkler, European J. Combinatorics 8 (1987), pp. 209-212.
  35. The metric structure of graphs: theory and applications, P. Winkler, Surveys in Combinatorics 1987/Invited Papers for the Eleventh British Combinatorial Conference, C. Whitehead (editor), Cambridge U. Press, 1987, pp. 196-221.
  36. Arithmetic progressions in partially ordered sets, W.T. Trotter and P. Winkler, ORDER 4 (1987), pp. 37-42.
  37. Recent results in the theory of random orders, P. Winkler, Applications of Discrete Mathematics, R.D. Ringeisen and F.S. Roberts (editors), SIAM Publications, Philadelphia, PA, 1988, pp. 59-64.
  38. The longest chain among random points in Euclidean space, B. Bollobás and P. Winkler, Proc. Amer. Math. Soc. 103:2 (1988), pp. 347-353.
  39. The complexity of metric realization, P. Winkler, SIAM J. Disc. Math. 1:4 (1988), pp. 552-559.
  40. A Ramsey-type theorem for orderings of a graph, V. Rödl and P. Winkler, SIAM J. Disc. Math. 2:3 (1989), pp. 402-406.
  41. A counterexample in the theory of random orders, P. Winkler, ORDER 5 (1989), pp. 363-368.
  42. Bandwidth versus bandsize, P. Erdõs, P. Hell and P. Winkler, Graph Theory in Memory of G.A. Dirac, L.D. Andersen et al. (editors), North-Holland, Amsterdam, 1989, pp. 117-129.
  43. Sphere Orders, G. Brightwell and P. Winkler, ORDER 6 (1989), pp. 235-240.
  44. Mean distance in a tree, P. Winkler, Discrete Applied Math. 27 (1990), pp. 179-185.
  45. Maximum hitting time for random walks on graphs, G. Brightwell and P. Winkler, J. Random Structures and Algorithms 1:3 (1990), pp. 263-276.
  46. Maximal chains and antichains in Boolean lattices, D. Duffus, B. Sands and P. Winkler, SIAM J. Disc. Math., 3:2 (1990), pp. 197-205.
  47. Extremal cover time for random walks on trees, G. Brightwell and P. Winkler, J. Graph Theory 14:5 (1990), pp. 547-554.
  48. Extremal Problems for Random Walks on Graphs, P. Winkler, Graph Theory Notes of New York XIX, New York Acad. Sci., 1990, pp. 18-25.
  49. Computing with snakes in directed networks of automata, S. Even, A. Litman and P. Winkler, Proc. 31st IEEE Symp. on the Foundations of Computer Science, 1990, pp. 740-745, Extended Abstract.
  50. Random intervals, J. Justicz, E. Scheinerman and P. Winkler, Amer. Math. Monthly 97:10 (1990), pp. 881-889.
  51. Counting linear extensions is #P-complete, G. Brightwell and P. Winkler, Proc. 23rd ACM Symposium on the Theory of Computing, 1991, pp. 175-181, Extended Abstract.
  52. On a random walk problem arising in self-stabilizing token management, P. Tetali and P. Winkler, Proc. 10th ACM Symp. on the Principles of Distributed Computing, 1991, pp. 273-280, Extended Abstract.
  53. On the number of k-realizations of an ordered set, D. Duffus and P. Winkler, ORDER 7:3 (1991), pp. 267-273.
  54. The number of t-wise balanced designs, C. Colbourn, D. Hoffman, K. Phelps, V. Rödl and P. Winkler, Combinatorica 11:3 (1991), pp. 207-218.
  55. Random orders of dimension 2, P. Winkler, ORDER 7:4 (1991), pp. 329-339.
  56. On the number of Eulerian orientations of a graph, M. Mihail and P. Winkler, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 138-145, Extended Abstract.
  57. On playing "twenty questions" with a liar, A. Dhagat, P. Gacs and P. Winkler, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 16-22, Extended Abstract.
  58. Counting linear extensions, G. Brightwell and P. Winkler, ORDER 8:3 (1992), pp. 225-242.
  59. Target shooting with programmed random variables, G. Brightwell, T. Ott and P. Winkler, Proc. 24rd ACM Symp. on the Theory of Computing, 1992, pp. 691-698, Extended Abstract.
  60. Three thresholds for a liar, J. Spencer and P. Winkler, Combinatorics, Probability and Computing 1:1 (1992), pp. 81-93.
  61. Recent results: proof checking and approximability, P. Winkler, Newsletter of the SIAM Activity Group on Discrete Mathematics 2:4 (1992), pp. 7-8, Expository.
  62. Fast information sharing in a complete network, V.S. Sunderam and P. Winkler, Disc. Appl. Math. 42 (1993), pp. 75-86.
  63. Collisions among random walks on a graph, D. Coppersmith, P. Tetali and P. Winkler, SIAM J. Disc. Math. 6:3 (1993), pp. 363-374.
  64. Simultaneous reversible Markov chains, P. Tetali and P. Winkler, Combinatorics, Paul Erdõs is Eighty Vol. 1, D. Miklos, V.T. Sos and T. Szonyi (editors), Janos Bolyai Mathematics Institute, Budapest, 1993, pp. 433-452.
  65. A note on the last new vertex visited by a random walk, L. Lovász and P. Winkler, J. Graph Theory 17:5 (Nov. 1993), pp. 593-596.
  66. Random structures and zero-one laws, P. Winkler, Finite and Infinite Combinatorics of Sets and Logic, N. Sauer, R. Woodrow and B. Sands (editors), NATO Advanced Science Institutes Series, Kluwer Academic Publishers, Kluwer Academic, Dordrecht, 1993, pp. 399-420.
  67. Interval orders and linear extension cycles, G. Brightwell, P. Fishburn and P. Winkler, Ars Combinatoria 36 (1993), pp. 283-288.
  68. Bounding the vertex cover number of a hypergraph, G.-L. Ding, P.D. Seymour and P. Winkler, Combinatorica 14:1 (1994), pp. 23-34.
  69. Control of acousto-optical tunable filters in a 4x4 Benes network, P. Winkler, Bellcore Technical Memorandum TM-24252, 1994.
  70. On the size of a random maximal graph, P. Erdõs, S. Suen and P. Winkler, J. Random Structures and Algorithms 6:2-3 (1995), pp. 309-318.
  71. Packing random intervals, E.J. Coffman, B. Poonen and P. Winkler, Prob. Theory Relat. Fields 102 (1995), pp. 105-121.
  72. The spanning tree enumeration problem for digraphs, N. Dean, A.K. Kelmans, K.-W. Lih, W.A. Massey and P. Winkler, Graph Theory, Combinatorics, and Applications, Y. Alavi and A. Schwenk (editors), John Wiley & Sons, New York, 1995, pp. 277-287.
  73. Monotone Gray codes and the middle levels problem, C. Savage and P. Winkler, J. Comb. Theory (A) 70:2 (May 1995), pp. 230-248.
  74. Efficient stopping rules for Markov chains, L. Lovász and P. Winkler, Proc. 27th ACM Symp. on the Theory of Computing, 1995, pp. 76-82, Extended Abstract.
  75. Exact mixing in an unknown Markov chain, L. Lovász and P. Winkler, Electronic J. Comb. 2 (1995), Paper R15.
  76. A key escrow system with warrant bounds, A. Lenstra, P. Winkler and Y. Yacobi, CRYPTO '95, 1995, pp. 197-207, Extended Abstract.
  77. Mixing of random walks and other diffusions on a graph, L. Lovász and P. Winkler, Surveys in Combinatorics, 1995, P. Rowlinson (editor), 1995, pp. 119-154, London Math. Soc. Lecture Note Series 218.
  78. Target shooting with programmed random variables, G. Brightwell, T.J. Ott and P. Winkler, Annals of Appl. Prob. 3:5 (1995), pp. 834-853.
  79. On the isolation of a common secret, D. Beaver, S. Haber and P. Winkler, The Mathematics of Paul Erdõs Vol. II, R. Graham and J. Nesetril (editors), Springer-Verlag, Berlin, 1996.
  80. Comparing information without leaking it: simple solutions, R. Fagin, M. Naor and P. Winkler, Communications of the A.C.M. 39:5 (1996), pp. 77-85.
  81. On the number of Eulerian orientations of a graph, M. Mihail and P. Winkler, Algorithmica 16 (1995), pp. 402-414.
  82. Multiple cover time, D. Zuckerman and P. Winkler, Random Structures and Algorithms 9 (1996), pp. 403-411.
  83. Shuffling biological sequences, D. Kandel, Y. Matias, R. Unger and P. Winkler, Disc. Appl. Math. 71 (1996) (special issue on Computational Molecular Biology), pp. 171-185.
  84. Mean distance and minimum degree, M. Kouider and P. Winkler, J. Graph Theory 25:1 (May 1997), pp. 95-99.
  85. Computing with snakes in directed networks of automata, S. Even, A. Littman and P. Winkler, J. Algorithms 24 (1997), pp. 158-170.
  86. Mixing times for uniformly ergodic Markov chains, D. Aldous, L. Lovász and P. Winkler, Stochastic Processes and their Applications 71 (1997), pp. 165-185.
  87. The ring loading problem, A. Schrijver, P.D. Seymour and P. Winkler, SIAM J. Discrete Math. 11:1 (1998), pp. 1-14.
  88. Reversal of Markov chains and the forget time, L. Lovász, Combinatorics, Probability and Computing 7:1 (1998), pp. 189-204.
  89. Ramsey theory and sequences of random variables, W.T. Trotter and P. Winkler, Combinatorics, Probability & Computing 7:1 (1998), pp. 221-238.
  90. Ring Routing and Wavelength Translation, G. Wilfong and P. Winkler, Proc. Symp. on Discrete Algorithms, 1998, pp. 333-341 (extended abstract).
  91. Mixing times, P. Winkler and L. Lovász, Microsurveys in Discrete Probability, D. Aldous and J. Propp, eds., DIMACS Series in Discrete Math. and Theoretical Computer Science 41, Amer. Math. Soc., Providence RI, 1998, pp. 85-134.