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.