Workshop on Randomized Algorithms

     Weizmann Institute Dec 20-22nd.



                      SCHEDULE 
                     ====================


Sunday, December 20
-------------------

9:45 - 10:15  Coffee

10:15 - 11:00 Uri Zwick  -  Approximation algorithms for MAX CUT and MAX SAT

11:00 - 11:45 Russell Impagliazzo - A Method for Experimentally Exploring Search Spaces: 			    The Case of Graphs with Small Planted Bisections 

12:00 - 12:45   Moni Naor - Oblivious Transfer                              
   
   Lunch 

14:45 - 15:45 Omer Reingold  - On Extractors and Pseudo-Randomness 

15:45 -16:15 Coffee Break

16:15- 16:45  Thore Husfeldt - Marked Ancestors Problems                  


16:45-  17:30 Marek Karpinksi  - On Some Tighter Inapproximability Results 




Monday, December 21
-------------------

9:30 - 10:15 Miklos Santha - Approximate Testing with Relative Error

10:15- 10:45 Coffee Break

10:45 - 11:30 Yuval Rabani - Searching for a near neighbor in high dimensional spaces

11:30 - 12:15  Robert  Krauthgamer - Finding and certifying a large hidden 
              clique in a semirandom graph
 
   Lunch 

14:45- 15:15 W. Fernandez De La Vega - A Randomized Approximation 
             Scheme for Metric MAX-CUT


15:15 - 16:00 Kobbi Nissim - Computationally Sound Proofs: 
                             Reducing the Number of Random Oracle Calls

16:00- 16:30 Coffee Break

16:30- 17:15  Benny Pinkas - Secure Multicast Communication



Tuesday, December 22
--------------------

10:00 - 10:45 Noga Alon   -   Efficient testing of large graphs            

10:45 - 11:15 Coffee Break 

11:15- 12:00   Leonard Schulman -  Quadratic Euclidean Clustering

12:00-12:45  Gil Kalai - Boolean functions: Influence, noise sensitivity, 
    measure concentration, Fourier expansions, applications and speculations.