DIMACS Workshop on Randomization Methods in Algorithm Design: Program
Friday, December 12, 1997
08:30--09:00 Continental Breakfast (each day)
09:00--09:05 Welcome from the DIMACS Director and the Organizers
09:05--09:10 Distinguished Speaker introduced by J. Rolim
09:10--10:00 Distinguished Lecture
Oded Goldreich,
"Combinatorial Property Testing (a survey)"
(joint work with Shafi Goldwasser and Dana Ron)
10:00--10:15 Break
Session F.A Chairman: Panos Pardalos
10:15--11:00 Vijay V. Vazirani,
"Randomized Voting Lemmas for Set Cover"
(joint work with S. Rajagopalan)
11:00--11:30 Eric Allender,
"Making Nondeterminism Unambiguous"
11:30--12:00 Aravind Srinivasan,
"Multicommodity Flow and Circuit Switching"
12:00--01:30 LUNCH
Session F.B Chairman: S. Rajasekaran
01:30--02:00 David Zuckerman,
"Weak random sources, random sampling,
and $BPP \subseteq PH$"
02:00--02:30 Ravi Boppana,
"Leader Election with Perfect Information"
02:30--03:00 Ted Theodosopoulos
"Some Remarks on the Optimal Level of Randomization
in Global Optimization"
03:00--03:30 Break
Session F.C Chairman: Jose Rolim
03:30--04:00 Yossi Matias,
"Title to be announced"
04:00--04:30 Santosh Vempala,
"Semi-definite programming based algorithms for minimum
bandwidth and other vertex-ordering problems"
04:30--05:00 Eric Baum,
"On genetic algorithms"
Saturday, December 13, 1997
Session Sa.A Chairman: S. Rajasekaran
08:00--08:45 Continental Breakfast
08:45--09:15 Paul Spirakis,
"Cover Times in stochastic graphs"
(joint work with J. Reif, M. Yung, S.Nikoletseas and C.
Kaklamanis)
09:15--09:45 R. Barve, E.F. Grove and Jeff Vitter,
"Practical parallel external mergesort using limited
randomization"
09:45--10:15 Michel Bender,
"Efficient Asynchronous Consensus with the Value-Oblivious
Adversary Schedule"
10:15--10:30 Break
Session Sa.B Chairman: S. Rajasekaran
10:30--11:00 DingZhu Du,
"On average complexity of group testing algorithms"
11:00--11:30 John Franco,
"Probabilistic Lower Bounds on the Complexity of Some Algorithms
for Satisfiability"
11:30--12:00 George Havas
"Randomized algorithms for multiple gcd calculation"
(joint work with Gene Cooperman and Joachim von zur Gathen)
12:00--01:30 LUNCH
Session Sa.C Chairman: Panos Pardalos
01:30--02:00 R. Battiti , Alan Bertossi , Romeo Rizzi,
"Randomized and Reactive Algorithms for the Graph Partitioning
Problem"
02:00--02:30 S.L. Martins, P.M.Pardalos, M.G.C. Resende, and C.C. Ribeiro,
"A Greedy Randomized Adaptive Search Procedure
for the Steiner Problem in Graphs"
02:30--03:00 Jonas Mockus, Audris Mockus, and Linas Mockus,
"Bayesian Approach for Randomization of Heuristic Algorithms
of Discrete Programming"
03:00--03:30 Break
Session Sa.D Chairman: Jose Rolim
03:30--04:00 Sanguthevar Rajasekaran,
"Computing on Optical Models"
04:00--04:30 Bill Steiger,
"On the Mixing rate of the Triangulation Walk"
(joint work with Mike Molloy and Bruce Reed)
04:30--05:00 Lydia Kavraki,
"A Randomized Approach to Robot Path Planning"
(joint work with D. Hsu, J-C. Latombe,
R. Motwani, and P. Raghavan)
Sunday, December 14, 1997
Session Su.A Chairman: Jose Rolim
08:00--08:45 Continental Breakfast
08:45--09:15 Ravi Kannan
"Low-Rank Approximations to Matrices"
09:15--09:45 Igor Pak,
"Constructive recognition of a gray box group
isomorphic to $S_n$ and Goldbach's Conjecture"
(joint work with S. Bratus)
09:45--10:15 Luca Trevisan,
"The Approximability of Non-Boolean Constraint Satisfaction
Problem"
(joint work with Maria Serna and Fatos Xhafa)
10:15--10:30 Break
Session Su.B Chairman: Jose Rolim
10:30--11:00 Prasad Tetali,
"Comparison of mixing rates of Markov chains"
11:00--11:30 Andrei Broder,
"Min-Wise Independent Permutations"
11:30--12:00 Klaus Jansen,
"An approximation scheme for scheduling
of parallel malleable tasks"
12:00--01:30 LUNCH
Session Su.C Chairman: Panos Pardalos
01:30--02:00 Howard Karloff,
"A 7/8-Approximation Algorithm for MAX 3SAT?"
02:00--02:30 Robert J. Vanderbei
"Randomization of the Parametric Self-Dual Simplex Method"
02:30--03:00 Maria Serna
"Sequential and Parallel Heuristics for the MinLA Problem"
(joint work with J. Diaz and J. Petit)
03:00--03:30 Salil Vadhan
"A Complete Problem for Statistical Zero-Knowledge"
(joint work with Amit Sahai)
03:30--04:00 Amit Sahai
"Honest-Verifier Statistical Zero-Knowledge
Equals General Statistical Zero-Knowledge"
04:00--04:30 Miklos Santha
"On the approximation of finding a(nother) Hamiltonian cycle
in cubic Hamiltonian graphs"
04:30--05:00 P.M.Pardalos
"Closing Statements"
Previous: Participation
Next: Registration
Index
DIMACS Home Page
Contacting the Center
Document last modified on October 26, 1998.