DIMACS Workshop on Probabilistic Analysis of Algorithms: Program

REVISED Program
(please note reception on Sunday evening
& banquet on Tuesday evening.)

SUNDAY, May 11, 1997

 9:30-10:20 AM    M. Steele         
                  Survey of Recent Results in the Probability
		  Theory of Euclidean Optimization Problems

10:20-10:40 AM    Coffee

10:40-11:05 AM    J. Yukich         
                  Limit theorems in geometric probability

11:05-11:30 AM    D. Simchi-Levi    
                  Probabilistic Analysis, Set-Partitioning and
	          Linear Programming

11:30-11:55 AM    K. Clarkson       
	          Nearest Neighbor Searching in Metric Spaces

11:55- 2:00 PM    Lunch

 2:00- 2:50 PM    J. Pach           
 	          Packing and covering problems

 2:50- 3:10 PM    Coffee

 3:10- 3:35 PM    J. Cai
                  Improving Ajtai's connection of average case
                  and worst case complexity for lattice problems
 
 3:35- 4:00 PM    S. Vempala   
	          Locality-preserving hashing in higher dimensions

 4:00- 4:10 PM    Break

 4:10- 4:35 PM    R. Vohra 
	          Approximating Integer Programs by Randomized Rounding

 4:35- 5:00 PM    A. Fundia 
	          Derandomizing Algorithms, Matchings and Coverings on 
	          Hypergraphs, Integer Programming

 5:00- 5:25 PM    D. Matula
	          On The Probability of Perfect Channel Assignment in 
	          Capacitated Multilayer Cellulal Networks with Uniform
	          Mobile Unit Distribution

 5:25 - 5:50      Susan Holmes
                  A nonreversible Markov Chain sampling method

 6:00 PM          Reception - Prospect House
                  Everyone attending the workshop is 
                    invited and there is no charge 


MONDAY, May 12, 1997

 9:30-10:20 AM 	  R. Sedgewick 
	          Open Problems in the Analysis of Sorting and
	          Searching Algorithms

10:20-10:40 AM 	  Coffee

10:40-11:05 AM 	  W. Szpankowski
	          TOWARDS ANALYTICAL INFORMATION THEORY:
	          Recent Results on Lempel-Ziv Data Compression
	          Algorithms

11:05-11:30 AM 	  S. Savari
	          Redundancy of the Lempel-Ziv Incremental
		  Parsing Rule

11:30-11:55 AM    J. Fill
	          Probabilistic analysis of self-organizing lists

11:55- 2:00 PM    Lunch

 2:00- 2:50 PM    L. Devroye
	          UNIVERSAL LIMIT LAWS FOR DEPTHS IN RANDOM TREES

 2:50- 3:10 PM    Coffee

 3:10- 3:35 PM    R. Smythe
	          Probabilistic analysis of string-matching algorithms

 3:35- 4:00 PM    R. Schott
         	  Algorithm analysis via diffusion processes

 3:45- 4:10 PM    Break

 4:10- 4:35 PM    P. Chassaing 
	          How many probes are needed to find out the
	          maximum, or the zeroes, of a random function

 4:35- 5:00 PM    M. Furer
	          Randomized Splay Trees

 5:00- 5:25 PM    A. Czumaj 
	          Randomized Allocation Processes

 5:25- 5:30 PM    Break

 5:30- 5:25 PM    H. Mahmoud
	          On tree-growing search strategies


TUESDAY, May 13, 1997

 9:30-10:20 AM 	  R. M. Karp
	          Probabilistic Analysis of Graph Partitioning
	          and Related Problems

10:20-10:40 AM 	  Coffee

10:40-11:05 AM    T. Warnow
	          Inferring big divergent trees from realistic
	          length biomolecular sequences

11:05-11:30 AM 	  L. Shepp
	          Discrete Tomography

11:30-11:55 AM 	  M. Luby
	          Practical Loss-Resilient Codes

11:55- 2:00 PM 	  Lunch

 2:00- 2:50 PM 	  E. Coffman
	          Average case of bin-packing

 2:50- 3:10 PM 	  Coffee

 3:10- 3:35 PM 	  M. Mitzenmacher 
	          Average Case Analyses of First Fit and Random
	          Fit Bin Packing

 3:35- 4:00 PM 	  L. Perkovic  
                  Edge coloring in polynomial time, on average
 
 4:00- 4:10 PM 	  Break

 4:10- 4:35 PM 	  N. Galli
	          Algorithmic and Combinatorial Aspects of the
	          Connectedness of Random Graphs

 4:35- 5:00 PM    D. Achlioptas
	          Coloring random graphs with a greedy list-coloring 
	          algorithm

 5:00- 5:25 PM    V. Priebe
	          Average case of shortest-paths problems in the
	          vertex-potential model

 5:25- 5:50 PM    D. S. Johnson
                  On the average case behavior of FFD and 
                  BFD under discrete distributions  
 
 6:30- 9:00 PM    BANQUET - Prospect Gardens
                   There is a $21.95 charge for those wishing
                   to attend the banquet, payable by check or
                   cash at the registration desk.  Please make
                   out checks to:  Princeton University
                  

 
WEDNESDAY, May 14, 1997

 9:30-10:20 AM    B. Pittel
	          Probabilistic analysis of graph-related algorithms:
	          Differential equations and exponential supermartingales

10:20-10:40 AM    Coffee

10:40-11:30 AM    C. McDiarmid
	          Minimum spanning trees in random graphs

11:30-11:35 AM    Break

11:35-12:00 PM    M. Jerrum
                  Data sensitive analysis and a posteriori
	          performance guarantees

12:00- 2:00 PM    Lunch

 2:00- 2:50 PM    L. Levin
	          Average Case Complexity

 2:50- 3:10 PM    Coffee

 3:10- 3:35 PM    J. Wang
	          Average Case Complexity

 3:35- 4:00 PM    M. Ruszinko
	          TBA

 4:00- 4:25 PM    D. Panario 
	          Average-case analysis of algorithms for
	          polynomials over finite fields

 4:25- 4:35 PM    Break

 4:35- 5:25 PM    M. Dyer 
	          Path coupling and approximate counting

Previous: Participation

Next: Registration

Index

DIMACS Homepage