Co-sponsored by the National Security Agency and Microsoft Research.
Monday, November 1
Session 1 9:00 -- 9:20 Breakfast and Registration 9:20 -- 9:30 Welcome and Greeting 9:30 -- 10:10 R. Karp, U. of Washington Matchings, Cores and Dense Subgraphs in Sparse Random Graphs 10:10 -- 10:50 Van Vu, Microsoft Approximation of the Independence Number 10:50 -- 11:10 Coffee Break Session 2 11:10 -- 11:50 T. Luczak, Adam Mickiewicz U./Emory U. Random Graphs and Positional Games 11:50 -- 12:30 C.R. Subramanian, Max-Planck Institute A BFS Approach to Partitioning Problems on Random Graphs 12:30 -- 2:00 Lunch Session 3 2:00 -- 2:40 A. Czumaj, Paderborn Towards an Algorithmic Version of the General Lovasz Local Lemma 2:40 -- 3:20 D. Matula, Southern Methodist U. A Cell Occupancy Sieve Algorithm Resolving Hardest Case Roundings of Floating Point Functions 3:20 -- 3:30 Break 3:30 -- 4:00 R. Venkatesan, Microsoft Random Cayley Graphs and Discrete Log 4:00 -- 4:30 Tea Session 4 4:30 -- 5:10 L. Levin, Boston U. The Tale of One-Way Functions 5:10 -- 5:50 S. Venkatesh, U.Penn Information Storage in Finite Memory
Tuesday, November 2
Session 1 9:00 -- 9:30 Breakfast and Registration 9:30 -- 10:10 M. Jerrum, U. of Edinburgh Case Studies in Torpid Mixing 10:10 -- 10:50 L. Goldberg, U. of Warwick An Extension of Path Coupling 10:50 -- 11:10 Coffee Break Session 2 11:10 -- 11:50 G. Lueker, U.C.Irvine Expected Length of Longest Common Subsequences 11:50 -- 12:30 L. Stougie, Eindhoven U. of Technology Fast Randomized Algorithms for Stochastic Programming Problems 12:30 -- 2:00 Lunch Session 3 2:00 -- 2:40 G. Sorkin, IBM A Biased Walk Through Simulated Annealing 2:40 -- 3:20 M. Furer, Penn State U. Approximating Permanents of Complex Matrices 3:20 -- 3:30 Break 3:30 -- 4:00 J. Spencer, Courant Institute Random Sequential Greedy 4:00 - 4:30 Tea Session 4 4:30 -- 5:10 S. Vempala, M.I.T. Inapproximability via the Probabilistic Method 5:10 -- 5:50 J. Yukich, LeHigh U. A survey of the probability theory of the Euclidean TSP 7:00 -- 9:00 Dinner at the Holiday Inn in South Plainfield
Wednesday, November 3
Session 1 9:00 -- 9:30 Breakfast and Registration 9:30 -- 10:10 C. Borgs, Microsoft Slow Mixing on the Hypercubic Lattice 10:10 -- 10:50 D. Achlioptas, Microsoft Mick gets more than pie 10:50 -- 11:10 Coffee Break Session 2 11:10 -- 11:50 J. Franco, U. of Cincinnati A Perspective on Certain Polynomial Time Solvable Classes of Satisfiability 11:50 -- 12:30 J. Kim, Microsoft Random 2SAT 12:30 -- 2:00 Lunch Session 3 2:00 -- 2:40 P. Winkler, Bell Labs Optimality and Greed in Dynamic Allocation 2:40 -- 3:20 Angelika Steger, Munich University of Technology Balanced Allocations: More balls than bins 3:20 -- 3:30 Break 3:30 -- 4:10 A. Rucinski, Adam Mickiewicz U./Emory U. Embedding Sparse Graphs into Dense Regular Graphs 4:10 -- 4:40 Tea Session 4 4:40 -- 5:20 E. Coffman, New Jersey Institute of Technology Interval Packing in One and Two Dimensions 5:20 -- 6:00 D. Johnson, AT&T Labs Average-Case Analysis of a Self-Organizing Bin Packing Algorithm
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage