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

Barcelona, Spain, 8-10 October 1998

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

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

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

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)

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

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

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

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

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

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