DIMACS Workshop on Property Testing

March 30 - April 2, 2009
DIMACS Center, CoRE Building, Rutgers University

Organizers:

Ilan Newman, Haifa University, ilan at cs.haifa.ac.il

Miklos Simonovits, Alfréd Rényi Institute of Mathematics, miki at renyi.hu

Mario Szegedy, Rutgers University, szegedy at cs.rutgers.edu

This workshop is jointly sponosored by Princeton University and the Center for Computational Intractability.

Workshop Program:

Monday, March 30, 2009

 8:30 -  9:10  Breakfast and Registration

 9:10 -  9:25  Welcome and Opening Remarks
               Fred Roberts, DIMACS Director

               Introduction
               Ilan Newman, Haifa University

 9:25 - 10:25  Low degree testing
               Alex Samorodnitsky

10:25 - 10:50  Break

10:50 - 11:20  On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream
               Funda Ergun, Simon Fraser University

11:25 - 11:55  Testing by Implicit Learning
               Ilias Diakonikolas, Columbia University

12:00 -  2:00  Lunch

 2:00 -  3:00  Random matrices: The distribution of the smallest singular
               values-an approach via testing
               Van Vu,  Rutgers University

 3:05 -  3:35  Testing Halfspaces
               Kevin Matulef, MIT

 3:35 -  4:00  Break

 4:00 -  4:30  Tolerant testing for nearly-sortedness and applications
               Arie Matsliah

Tuesday, March 31, 2009

 8:45 -  9:25  Breakfast and Registration
 
 9:25 - 10:25  Property Testing in the Dense Graph Model
               Asaf Shapira, Georgia Institute of Technology

10:25 - 10:50  Break

10:50 - 11:20  Approximate hypergraph partitioning and applications to regularity
               Eldar Fischer, Technion, Israel

11:25 - 11:55  TBA, Artur Czumaj

12:00 -  2:00  Lunch

 2:00 -  3:00  TBA, Laci Lovasz

 3:05 -  3:35  Green's Conjecture and Testing Linear Invariant Properties
               Asaf Shapira, Georgia Institute of Technology

 3:35 -  4:00  Break

 4:00 -  4:30  Property testing and graph limits
               Balazs Szegedy

 4:30          Dinner at DIMACS

Wednesday, April 1, 2009

 8:45 -  9:25  Breakfast and Registration

 9:25 - 10:25  Testing Global Properties of Distributions
               Ronitt Rubinfeld, MIT and Tel-Aviv University

10:25 - 10:50  Break

10:50 - 11:20  How to beat the Monte Carlo method
               Jozsef Beck, Rutgers University

11:25 - 11:55  Transitive-closure Spanners
               Sofya Raskhodnikova, Penn State University 

12:00 -  2:00  Lunch

 2:00 -  3:00  Algebraic Property Testing: A Survey
               Madhu Sudan,  MIT CSAIL 

 3:05 -  3:35  Constant time distributed algorithms, parameter and
               property testing on very large graphs of small vertex degrees.
               A measure theoretical approach
               Gabor Elek, Renyi Institute, Hungary

 3:35 -  4:00  Break

 4:00 -  4:30  TBA, Christian Sohler

 4:30 -  5:00  Sparse Random Linear Codes are Locally Decodable and Testable
               Tali Kaufman, MIT

Thursday, April 2, 2009

 8:45 -  9:25  Breakfast and Registration

 9:25 - 10:25  Property testing in sparse and general graphs
               Michael Krivelevich, Tel Aviv University

10:25 - 10:50  Break

10:50 - 11:20  Succinct representation of codes with applications to testing
               Elena Grigorescu, MIT

11:25 - 11:55  Very Local Self Correcting of Homomorphism and MPC Codes
               Adi Akavia, IAS

12:00 -  2:00  Lunch

 2:00 -  3:35  New Direct Product Code Testers, and PCPs
               Avi Wigderson 

 3:35 -  4:00  Break

 4:00 -  4:30  TBA, Vera T. Sos

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage