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 BreakSession F.A Chairman: Panos Pardalos10: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 LUNCHSession F.B Chairman: S. Rajasekaran01: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 BreakSession F.C Chairman: Jose Rolim03: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"

Session Sa.A Chairman: S. Rajasekaran08: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 BreakSession Sa.B Chairman: S. Rajasekaran10: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 LUNCHSession Sa.C Chairman: Panos Pardalos01: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 BreakSession Sa.D Chairman: Jose Rolim03: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)

Session Su.A Chairman: Jose Rolim08: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 BreakSession Su.B Chairman: Jose Rolim10: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 LUNCHSession Su.C Chairman: Panos Pardalos01: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.