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