R A N D O M   ' 9 8

2nd. International Workshop on Randomization and Approximation Techniques in Computer Science



Barcelona, Spain, 8-10 October 1998




Final Program



Wednesday, October 7, 1998

18:30-20:30
Registration and Reception
Sala del Llac

Thursday, October 8, 1998

Session 1: 9:00-10:30 Chair J. Rolim

9:00
Invited Talk:Disjoint Paths in Expander Graphs via Random Walks: A Short Survey
Alan M. Frieze
10:00
A Derandomization Using Min-Wise Independent Permutations
Andrei Broder (Digital SRC Palo Alto), Moses Charikar (Stanford University), and Michael Mitzenmacher (Digital SRC Palo Alto)
10:30
Coffee Break

Session 2: 11:00-13:00 Chair A. Frieze

11:00
An Algorithmic Embedding of Graphs via Perfect Matchings
Vojtech Rödl, Andrzej Rucinski and Michelle Wagner (Emory University, Atlanta)
11:30
Deterministic Hypergraph Coloring and Its Applications
Chi-Jen Lu (Massachusetts University, Amherst)
12:00
On the De-randomization of Space-Bounded Computations
Roy Armoni (The Hebrew University, Jerusalem)
12:30
Talagrand's Inequality and Locality in Distributed Computing
Devdatt P. Dubhashi (Indian Institute of Technology, Delhi)
13:00
Lunch

Session 3: 14:30-16:00 Chair S. Skyum

14:30
On-line Bin-Stretching
Yossi Azar, and Oded Regev (Tel Aviv University)
15:00
Combinatorial Linear Programming: Geometry Can Help
Bern Gärtner (ETH Zürich)
15:30
A note on bounding the mixing time by linear programming
Avy Sharell (Université Paris Sud, Orsay)
16:00
Coffee Break

Session 4: 16:00-18:30 Chair G. Sorkin

16:30
Robotic Exploration, Brownian Motion and Electrical Resistance
Israel A. Wagner , Michael Lindenbaum, and Alfred M. Bruckestein (Technion, Haifa)
17:00
Quicksort Again Revisited
Charles Knessl (University of Illinois, Chicago), and Wojciech Szpankowski (Purdue University)
17:30
On Balls and Bins with Deletions
Richard Cole (Courant Institute, New York), Alan Frieze , Bruce M. Maggs (Carnegie Mellon U.), Michael Mitzenmacher (Digital SRC, Palo Alto), Andrea W. Richa (Carnegie Mellon U.), Ramesh K. Sitamaran (Massachusetts U., Amherst), and Eli Upfal (Brown University)
18:00
``Balls into Bins'' -- A Simple and Tight Analysis
Martin Raab, and Angelika Steger (Technische Universität München)

Friday, October 9, 1998

Session 5: 9:00-10:30 Chair L. Goldberg

9:00
Invited Talk: Tornado Codes: Practical erasure codes based on random irregular graphs
Michael Luby
10:00
Use Approximation Hardness to Achieve Dependable Computation
Mike Burmester (Royal Holloway University, London), Yvo Desmedt, and Yongge Wang (University of Wisconsin)
10:30
Coffee Break

Session 6: 11:00-13:00 Chair M. Luby

11:00
Complexity of Sequential Pattern Matching Algorithms
Mireille Régnier (INRIA Rocquencourt), and Wojciech Szpankowski (Purdue University)
11:30
A Random Server Model for Private Information Retrieval
Yael Gertner, Shafi Goldwasser, and Tal Malkin
12:00
Almost Optimal (on the average) combinatorial algorithms for boolean matrix product witnesses, computing the diameter
C.R. Subramanian (Max-Planck Institute, Saarbrücken)
12:30
Randomized Lower Bounds for Online Path Coloring
Stefano Leonardi, and Andrea Vitaletti (Università di Roma ``La Sapienza'')
13:00
Lunch

Session 7: 14:30-16:00 Chair E. Shamir

14:30
Parallel Random Search and Tabu Search for the Minimal Consistent Subset Selection Problem
Vicente Cerverón, and Ariadna Fuertes (Universitat de València)
15:00
On various Cooling Schedules for Simulated Annealing Applied to the Job Shop Problem
K. Steinhöfel (GMD First, Berlin), A. Albrecht, and C.K. Wong (The Chinese University, Hong Kong)
15:30
A High Performance Approximate Algorithm for the Steiner Problem in Graphs
P. Guitart, and J.M. Basart (UAB Barcelona)
16:00
Coffee Break

Session 8: 16:30-18:30 Chair M. Serna

16:30
Invited Talk: Random Geometric Problems on [0,1]^2
Josep Díaz
17:30
A role of constraint in self-organization
Carlos Domingo (UPC Barcelona), Osamu Watanabe, and Tadashi Yamazaki (Tokyo Institute of Technology)
18:00
Second Order Methods for Distributed Approximate Single- and Multicommodity Flow
S. Muthukrishnan, and Torsten Suel (Bell Laboratories)
21:30
Workshop Dinner

Saturday, October 10, 1998

Session 9: 9:00-10:30 Chair J. Diaz

9:00
Invited Talk: On a simple sampling lemma--applications and analysis
Emo Welz
10:00
Constructive Bounds and Exact Expectations for the Random Assignment Problem
Don Coppersmith, and Gregory B. Sorkin
10:30
Coffee Break

Session 10: 11:00-12:30 Chair E. Welzl

11:00
The ``Burnside Process'' Converges Slowly
Leslie Ann Goldberg (University of Warwick), and Mark Jerrum (University of Edinburgh)
11:30
Fringe analysis of synchronized parallel algorithms on 2-3 trees
Ricardo Baeza-Yates (U. Chile), Joaquim Gabarró, and Xavier Messeguer (UPC Barcelona)
12:00
Sampling Methods Applied to Non-Boolean Optimization Problems
Gunnar Andersson (Royal Institute of Technology, Stockholm), and Lars Engebretsen
12:30
Closing