DIMACS Workshop on Property Testing

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

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
Presented under the auspices of the Special Focus on Hardness of Approximation.

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

Property Testing was implicitly introduced by Blum, Luby and Rubinfeld and explicitly by Goldreich Goldwasser and Ron. The subject has seen a breathtaking growth from a special purpose combinatorial tool, which was designed to randomly check with three queries whether a black box function is close to a linear form over GF(2), into a scientific field on its own. Its success is mainly due to the versatility of its applications that range from the theory of probabilistically checkable proofs and sub-linear algorithm design to combinatorics and large data sets. Its results have noticeable effect on established fields, like Ramsey theory and the theory of Boolean functions.

Property testing draws ideas from coding theory, extremal graph theory, Fourier analysis, and many other fields. This workshop will bring researchers together from all of the above fields.

We will offer expository talks with which we hope to engage students and established researchers alike. Of course, there will also be several reports on cutting edge results and ample time for free discussions.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on December 22, 2008.