DIMACS Workshop on Pseudorandomness and Explicit Combinatorial Constructions

October 12 - 15, 1999
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:

David Zuckerman, University of Texas at Austin, University of California at Berkeley, diz@cs.berkeley.edu

Russell Impagliazzo, University of California at San Diego, russell@cs.ucsd.edu

Amnon Ta-Shma, International Computer Science Institute, amnon@ICSI.Berkeley.EDU

Preliminary Program:

Tuesday, October 12

9:30 - 9:50    	Breakfast and Registration

9:50 - 10:00   	Welcome and Greeting
		Michael Saks, Organizer of the DIMACS Special Year on Computational Intractability

10:00 - 11:00   Invited talk: Luca Trevisan, Columbia University
               	Extractors and Pseudorandom Generators.

11:00 - 11:30	Break

11:30 - 12:15   Omer Reingold, AT&T Research        
               	Error Reduction for Extractors.        

12:15 - 2:30	Lunch

2:30 - 3:15     Ran Raz, Weizmann Institute               
               	On Recycling the Randomness of the States in Space 
               	Bounded Computation.

3:15 - 3:30	Break

3:30 - 4:15     Chi-Jen Lu, Academia Sinica              
               	Pseudorandom Generators for Combinatorial Rectangles.

4:15 - 4:30	Break

4:30 - 5:00 	Aravind Srinivasan, Bell Labs      
               	Min-Wise Independent Permutation Families.



Wednesday,  October 13

9:00 - 9:30	Breakfast and registration

9:30 - 10:15  	Johan Hastad, Royal Institute of Technology, Sweden           
               	Security of All Individual RSA Bits.

10:15 - 10:25	Break

10:25 - 11:10 	Moni Naor, Stanford University and Weizmann Institute
               	Pseudo-Random Functions, Factoring and Assumptions    

11:10 - 11:30 	Break

11:30 - 12:30  	Invited talk: Noga Alon, Tel Aviv University
               	Ramsey Type Graphs.

12:30 - 2:30    Lunch

2:30 - 3:15   	Tibor Szabo, University of Illinois at Urbana-Champaign       
               	Norm Graphs: Variations and Applications.

3:15 - 3:30	Break

3:30 - 4:15   	Alex Lubotzky, Hebrew University and Yale University       
               	Groups and Expanders.

4:15 - 4:30	Break

4:30 - 5:15   	Igor Pak, Yale University
               	Generating Random Group Elements by Product Replacement Algorithm

7:00 - 8:30     Dinner at the Holiday Inn in South Plainfield



Thursday, October 14

9:00 - 9:30	Breakfast and registration

9:30 - 10:15  	Salil Vadhan, MIT            
               	Pseudorandom Generators Without the XOR Lemma.

10:15 - 10:25 	Break

10:25 - 11:10 	Madhu Sudan, MIT           
               	List decoding: Algorithms and Applications.

11:10 - 11:30   Break

11:30 - 12:30 	Invited talk: Amin Shokrollahi, Bell Labs
               	Codes Over Algebraic Curves.
           
12:30 - 2:30	Lunch

2:30 - 3:15     Juergen Bierbrauer, Michigan Technological University
               	From Algebraic-Geometric Codes to Limited Bias and Dependence.

3:15 - 3:30	Break

3:30 - 5:00 	Open problems session. 



Friday, October 15

9:00 - 9:30	Breakfast and registration

9:30 - 10:15    Russell Impagliazzo
               	Derandomization Under a Uniform Assumption.

10:15 - 10:25	Break

10:25 - 11:10	Ronen Shaltiel, Hebrew University          
               	Extractors and Pseudo-Random generators with optimal seed size.

11:10 - 11:30	Break

11:30 - 12:30 	Invited talk: Avi Widgerson, IAS and Hebrew University
               	Open Problems.

12:30 - 2:30	Lunch
 
2:30 - 3:15   	Peter Bro Miltersen, University of Aarhus
               	Derandomizing Arthur-Merlin games using hitting sets.

3:15 - 3:30	Break

3:30 - 4:15  	Adam Klivans, MIT            
               	Boosting and Hard-Core Sets.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage