Special Session on
Applied Probabilistic Combinatorics
(Complete, Revised Program)
Organizers:
Please note that the program below includes three
additional talks not shown in the AMS program:
-
Friday 6:00 p.m.-6:30 p.m. Sampath Kannan Efficient
Algorithms for Inverting Evolution
-
Sunday 12:00 p.m.-12:30 p.m. David Levin A
Phase Transition in Random Walks on Stochastic Scenery
-
Sunday 12:30 p.m.-1:00 p.m. J Michael Steele Construction
of Combinatorial Gradients
Since these talks are not listed elsewhere, I have included their abstracts
here. I have also listed the AMS meeting's opening invited talk,
by Bela Bollobas, since it is likely to be of particular interest to many
of you.
Here is a
map of the UNCC campus.
-Gregory Sorkin
October 13, 1999
Click on session title to display the abstract in PDF
Format. PDF Format is read with Adobe
Acrobat Reader which may be downloaded for free.
-
Friday October 15, 1999, 1:15 p.m.-2:15
p.m.
Invited Address
Welcome and Opening Remarks
Room 110, Storrs Architecture Building
Phase transitions in combinatorial
structures.
Room 110, Storrs Architecture Building
B\'ela Bollob\'as*, University of Memphis and Cambridge University
(949-05-04)
-
Friday October 15, 1999, 2:30 p.m.-6:20 p.m.
Special Session on Applied Probabilistic Combinatorics, I
Room 105, Denny Hall
Organizers:
Bela Bollob\'as, University of Memphis bollobas@msci.memphis.edu
Gregory Sorkin, IBM T.J. Watson Research Center sorkin@watson.ibm.com
-
2:30 p.m.
Coalescent trees and the
age of a mutation.
Robert C Griffiths, University of Oxford
Simon Tavar\'e*, University of Southern California
(949-60-71)
-
3:00 p.m.
Random Three-Dimensional
Tilings of Aztec Octahedra and Tetrahedra: An Extension of Domino Tilings.
Dana Randall*, Georgia Institute of Technology
Gary Yngve, Georgia Institute of Technology
(949-05-182)
-
3:30 p.m.
The sizes and speeds of
properties of graphs.
David Weinreich*, The University of Memphis
Bela Bollobas, The University of Memphis and Cambridge University
Jozsef Balog, The University of Memphis
(949-05-227)
-
4:00 p.m.
Graphical Representations
of the Potts Model in a Magnetic Field.
Marek Biskup, Microsoft Research
Christian Borgs*, Microsoft Research
Jennifer T Chayes, Microsoft Research
Roman Kotecky, Center for Theoretical Study
(949-82-226)
-
4:30 p.m.
Discounted Reward Markov
Decision Process is Undecidable.
Anne E Condon*, University of British Columbia
(949-68-109)
-
5:00 p.m.
Random matchings which induce
Hamilton cycles, and Hamiltonian decompositions of random regular graphs.
Jeong Han Kim*, Microsoft Research
Nick C. Wormald, University of Melbourne
(949-05-84)
-
5:30 p.m.
0-1 Laws for Single Molecules.
Bud Mishra*, Courant Institute, NYU
(949-05-67)
-
6:00 p.m.
Efficient Algorithms for Inverting Evolution.
Martin Farach, Rutgers University
Sampath Kannan*, University of Pennsylvania
-
Evolution is a stochastic process which operates on the DNA
of species. The evolutionary process leaves tell-tale signs in the
DNA which can be used to construct phylogenies, or evolutionary trees,
for a set of species. So called Maximum Likelihood Estimations (MLE)
methods seek the evolutionary tree which is most likely to have produced
the DNA under consideration. While these methods are widely accepted
and intellectually satisfying, they are computationally intractable.
We offer a simple polynomial time algorithm for finding a tree which approaches
the most likely tree, complementing our result with a lower bound on how
well any algorithm can do, no matter its computational complexity.
We thus show that our simple approach is close to optimal in terms of the
amount of DNA needed to find a "good" tree.
-
Joint work with Andris Ambainis, Rick Desper and
Martin Farach-Colton.
-
Saturday October 16, 1999, 8:30 a.m.-10:50
a.m.
Special Session on Applied Probabilistic Combinatorics, II
Room 105, Denny Hall
Organizers:
Bela Bollob\'as, University of Memphis bollobas@msci.memphis.edu
Gregory Sorkin, IBM T.J. Watson Research Center sorkin@watson.ibm.com
-
8:30 a.m.
DNA sequencing, Euler circuits,
and graph polynomials.
Richard Arratia, U.S.C.
Bela Bollobas, Univ. of Cambridge / Memphis Univ.
Don Coppersmith, IBM Watson Research Ctr.
Gregory B Sorkin*, IBM Watson Research Ctr.
(949-05-83)
-
9:00 a.m.
The interlace polynomial:
a new graph polynomial.
Richard Arratia, University of Southern California, Los Angeles
CA
B\'ela Bollob\'as*, University of Memphis, Memphis TN
Gregory B Sorkin, IBM T. J. Watson Research Center
(949-05-218)
-
9:30 a.m.
On the impossibility of
closed-form partition functions for the 3D Ising model across lattices.
Sorin I Istrail*, Sandia National Laboratories
(949-82-153)
-
10:00 a.m.
A Survey of Subshifts of
Finite Type and Measures of Maximal Entropy.
Jeffrey E Steif*, Georgia Institute of Technology
(949-05-69)
-
10:30 a.m.
Phylogeny needs more probability
for sure.
Laszlo A Szekely*, University of South Carolina
(949-92-122)
-
Saturday October 16, 1999, 2:30 p.m.-6:40
p.m.
Special Session on Applied Probabilistic Combinatorics, III
Room 105, Denny Hall
Organizers:
Bela Bollob\'as, University of Memphis bollobas@msci.memphis.edu
Gregory Sorkin, IBM T.J. Watson Research Center sorkin@watson.ibm.com
-
2:30 p.m.
Anisotropic Self-Avoiding
Walks: The Existence of a Phase with Nontrivial Negative Masses.
Christian H Borgs, Microsoft Research
Jennifer T Chayes*, Microsoft Research
Chris King, Northeastern University
Neal Madras, York University
(949-60-225)
-
3:00 p.m.
Equivalent Conditions of
Regularity.
Yoshiharu Kohayakawa, University of Sao Paulo, Brasil
Vojtech Rodl, Emory University
Jozef Skokan*, Emory University
(949-05-251)
-
3:30 p.m.
Broadcasting on Trees and
the Ising Model.
William Evans, U. Arizona
Claire Kenyon, LRI, Universite de Paris-Sud
Yuval Peres, Hebrew University and U. C. Berkeley
Leonard J Schulman*, Georgia Tech
(949-60-95)
-
4:00 p.m.
Edge disjoint paths in expander
graphs.
Alan M Frieze*, Carnegie Mellon University
(949-68-85)
-
4:30 p.m.
Interruptible perfect sampling.
Mark L Huber*, Stanford University
(949-60-104)
-
5:00 p.m.
Correlation decay in random
tilings.
Rick Kenyon, Orsay
Robin Pemantle*, Ohio State University
(949-05-252)
-
5:30 p.m.
Upper and lower bounds for
the time constant of first-passage percolation.
Sven Erick Alm*, Dept. of Mathematics, Uppsala University
(949-60-142)
-
6:20 p.m.
Discussion
-
Sunday October 17, 1999, 9:30 a.m.-12:50
p.m.
Special Session on Applied Probabilistic Combinatorics, IV
Room 105, Denny Hall
Organizers:
Bela Bollob\'as, University of Memphis bollobas@msci.memphis.edu
Gregory Sorkin, IBM T.J. Watson Research Center sorkin@watson.ibm.com
-
9:30 a.m.
Counting Independent Sets
in the Grid.
Neil J Calkin*, Clemson University
(949-05-235)
-
10:00 a.m.
Mick gets more than pie.
Dimitris Achlioptas*, Microsoft Research
(949-05-70)
-
10:30 a.m.
Confirming Kleitman-Winston
conjecture on the largest coefficient in a q-Catalan number.
Boris G Pittel*, Department of Mathematics, Ohio State University,
Columbus, Ohio, 43210- 1174
Jeong Han Kim, Microsoft
(949-05-168)
-
11:00 a.m.
Bounds for Critical Probabilities
in Percolation Models.
John C Wierman*, Johns Hopkins University
(949-05-52)
-
11:30 a.m.
Entanglement in 3D percolation.
Olle Haggstrom*, Chalmers University of Technology
(949-60-155)
-
12:00 p.m.
A Phase Transition in Random Walks on Stochastic
Scenery.
David A Levin*, University of Connecticut
-
Suppose that a biased coin is tossed at return times of a
random walk on an infinite graph to the origin, and a fair coin is tossed
at all other times. (We observe only the results of the coin tosses, and
NOT the location of the random walk.) When can this (rarely-) biased sequence
be distinguished from a sequence of IID fair coin tosses? Let $u_n$
denote the chance of the walk being at the origin at time $n$. Harris and
Keane (1997) showed that if ${u_n}$ is not square-summable, then the (rarely-)
biased coin tosses can be distinguished from fair coin tosses; they also
proved a partial converse. Harris and Keane conjectured that distinguishability
should not depend on the bias, but only on the square-summability of ${u_n}$.
-
I will describe the surprising resolution of this conjecture,
and sketch results concerning random walks on (stochastic) scenery on $Z$.
-
This is joint work with Robin Pemantle and Yuval Peres.
-
12:30 p.m.
Construction of Combinatorial Gradients.
J Michael Steele*, Wharton School, University of Pennsylvania
-
Talagrand's theory of concentration inequalities has a remarkable
range of applications to problems that occur in many areas of optimization,
combinatorics, and physical science. Often the key to a successful application
of this theory is the construction of what can be called a "combinatorial
gradient." This is a specially structured upper bound on the change in
combinatorial functional that takes place when one "changes some of the
points" that make up the functional's arguments. This talk will illustrate
some useful methods for construction of such bounds.
AMS Sectional Meetings | AMS
National Meetings | AMS International
Meetings | Inquiries: meet@ams.org