Property Testing is the study of super-fast (randomized) algorithms for approximate decision making. These algorithms are given direct access to items of a huge data set, and determine whether this data set has some predetermined (global) property or is far from having this property. Remarkably, this approximate decision is made by accessing a small portion of the data set. Property Testing has been a subject of intensive research in the last couple of decades, with hundreds of studies conducted in it and in closely related areas. Indeed, Property Testing is closely related to Probabilistically Checkable Proofs (PCPs), and is related to Coding Theory, Combinatorics, Statistics, Computational Learning Theory, Computational Geometry, and more.

Abstracts of all talks are available in the
official
brochure of the mini-workshop.

**(In addition,
extended abstracts of most papers are available below.)**

- Amy Wang: Welcoming comments.
- Rocco Servedio: Testing by Implicit Learning
- Kevin Matulef: Testing (subclasses of) Linear Threshold Functions

- Eric Blais: Testing juntas and function isomorphism.
- Michael Krivelevich: Hierarchy Theorems for Property Testing.

- Ilan Newman: a survey on property testing in the 'underlying graph' or 'massively parametrized' model [presentation in PPTX and PDF]
- Sofya Raskhodnikova: Transitive-Closure Spanners with Applications to Monotonicity Testing
- Christian Sohler: Testing Euclidean Spanners

Panelists: Avrim Blum, Bernard Chazelle, and Rocco Servedio.

Bernard advocated an attempt to provide a sublinear time analysis of dynamic systems, which may consist of selecting few objects and tracing their activity during time. Avrim emphasised the high cost of queries (rather than random examples) in typical learning applications, and I suggested to consider a two-parameter complexity measure that separates the number of random examples from the number of actual queries. Rocco suggested to try to relate property testing to agnostic learning (rather than to standard learning), and highlighted the open problem of tolerant testing of half planes.

- Madhu Sudan: Invariance in Property testing
- Victor Chen: Testing Linear-Invariant Non-Linear Properties

- Asaf Shapira: Testing Linear Invariant Properties
- Noga Alon: On constant time approximation of invariants of bounded degree graphs
- Ronitt Rubinfeld: Maintaining a large matching or a small vertex cover
- Krzysztof Onak: External Sampling

- Krzysztof Onak: Sublinear Graph Approximation Algorithms
- Michael Saks: Local Monotonicity Reconstruction
- Ronitt Rubinfeld: Testing properties of distributions: a survey

Panelists: Madhu Sudan, Noga Alon, and Ronitt Rubinfeld.

Noga focused on the "global vs local" nature of property testing that is closely related to a main theme in combinatorics initiated by Erdos in the 1950's. He noted that a tester of $k$-colorability is implicit in work of the 1980's, but the query bound obtained there is a tower of exponents in the proximity parameter. Answering a question, Noga kind of suggested the challenge of testing triangle-freeness in $2^{O(1/\eps)^2}$ queries. (Recall that the currently best known bound is a tower of exponents in $poly(1/\eps)$.) Ronitt reported on the awakening of interest of statisticians in the effect of the size of the domain (of values). (Traditionally, Statistics is concerned with the effect of the size of the universe (sample space), whereas we are concerned with the effect of the number of values obtained in this space.) Still there are significant cultural differences, since in Statistics one often makes (implicit) assumptions about the distribution and/or assumes that the distribution itself is selected at random among some possibilities (hence "likelihood" is relevant). Ronitt also pointed out possible applications to areas that use Statistics such as natural language processing and data bases. Madhu pointed out that sublinear time algorithms arise naturally in the context of coding theory. Shafi advocated the study of property testing of algebraic (and number theoretic) problems beyond linearity and low-degree properties. A concrete example may be testing that a polynomial (given by its evaluations) is an irreducible polynomial. Can a tester be significantly more efficient than polynomial interpolation?

- Prahladh Harsha: Composition of low-error 2-query PCPs using decodable PCPs
- Victor Chen: A Hypergraph Dictatorship Test with Perfect Completeness
- Michael Krivelevich: Comparing the strength of query types in property testing

- Shubhangi Saraf: Some recent results on testing of sparse linear codes
- Swastik Kopparty: Optimal Testing of Reed-Muller Codes

- Eli Ben-Sasson: Limiting the rate of locally testable codes
- Tali Kaufman: Symmetric LDPC codes and local testing
- Artur Czumaj: Testing monotone continuous distributions on high-dimensional real cubes [see also presentation in PDF]
- Krzysztof Onak: The Query Complexity of Edit Distance
- Sofya Raskhodnikova: Testing and Reconstruction of Lipschitz Functions with Applications to Privacy
- Oded Goldreich: Algorithmic Aspects of Property Testing in the Dense Graphs Model.

- Prahladh Harsha on decoding in the low-error regime
- Ron Rivest on possible applications of property testing to the security evaluation of hashing functions.

- Artur Czumaj and Christian Sohler: Sublinear-time algorithms
- Oded Goldreich: a tentative preface for a tentative volume
- Oded Goldreich: Short Locally Testable Codes and Proofs - A Survey in Two Parts
- Oded Goldreich: Introduction to Testing Graph Properties

See the official brochure (in PDF) and Oded Goldreich's homepage.