From Erdos to Algorithms (Applications of the ``Probabilistic Method'')
A joint DIMACS - DIMATIA workshop
June 8 - 10, 1998
DIMACS Center, CoRE Building, Rutgers University, Piscataway, NJ
- Organizers:
Jarik Nesetril, DIMATIA, Co-Chair,
nesetril@kam.ms.mff.cuni.cz
Joel Spencer, NYU, Co-Chair, spencer@cs.nyu.edu
Ron Graham, AT&T Labs - Research, rlg@research.att.com
Jiri Matousek, DIMATIA
Pavel Valtr, DIMATIA
valtr@dimacs.rutgers.edu
Preliminary Program of Workshop:
Monday, June 8
- 9-9:50 Vera Sos (Hungarian Academy of Sciences)
- $\{n\alpha\}$ sequences: from Erd\H os to algorithms.
- 10:30-11 Joseph Beck (Rutgers)
- Multidimensional tic-tac-toe
- 11-11:30 Lenore Cowen (Johns Hopkins)
- Randomized Algorithms for Approximate Distance
- 11:30-12 Mike Molloy (U. Toronto)
- TBA
- 2:00-2:30 Prasad Tetali (Georgia Tech)
- $\lambda_infty$, vertex expansion and concentration."
- 2:30-3:00 Ehud Friedgut (Hebrew Univeristy/IAS)
- Ramsey properties of Random Graphs
- 3:00-3:30 Joel Spencer (Courant Institute)
- Report on new B bound of Srinivasan and Radhakrishnanz
- 4:00-4:30 Van Vu (Yale)
- Small complete arcs in finite projective planes.
- 4:30-5:00 Josep Diaz (Barcelona)
- Layout problems on Random graphs
Tuesday, June 9
- 9-9:50 Laszlo Lovasz (Yale)
- Flows andRandom Walks
- 10-10:30 David Karger (MIT)
- Some Probabilistic Methods for Cuts in Graphs
- 10:30-11 Alan Frieze (Carnegie Mellon)
- Random minimum length spanning trees in regular graphs
- 11-11:30 Lucek Kucera (Charles/Prague)
- Random Graphs in Expected Case Analysis
- 2-2:30 Fan Chung (U. Penn)
- TBA
- 2:30-3:00 Pavel Valtr (Charles/Prague)
- Several Results Related to the Erdos-Szekeres Theorem
- 3:00-3:30 Greg Sorkin (IBM Yorktown Heights)
- The Random Assignment Problem
Wednesday, June 10
- 9-9:30 Michael Krivelevich (IAS)
- The Choice Number of Dense Random Graphs
- 9:30-10 Yoshihara Kohayakawa (IME/Brazil)
- Random Sperner-type Results
- 10:30-11 Jeff Kahn (Rutgers)
- TBA
- 11-11:30 Jeong-Han Kim (Microsoft)
- TBA
- 2-2:30 Peter Winkler (Lucent)
- Random Colorings of a Tree
- 2:30-3 Gyorgy Elekes (Eotvos/Budapest)
- TBA
Previous: Participation
Next: Registration
Index
DIMACS Homepage
Contacting the Center
Document last modified on April 13, 1998.