Property Testing

Editor's Introduction.- A Brief Introduction to Property Testing.- The Program of the Mini-Workshop.- Surveys.- Limitation on the Rate of Families of Locally Testable Codes.- Testing Juntas.- Sublinear-time Algorithms.- Short Locally Testable Codes and Proofs: A Survey in Two Parts.- Introduction to Testing Graph Properties.- Property Testing of Massively Parameterized Problems.- Sublinear Graph Approximation Algorithms.- Transitive-Closure Spanners.- Testing by Implicit Learning.- Invariance in Property Testing.- Extended Abstracts.- Testing Monotone Continuous Distributions on High-Dimensional Real Cubes.- On Constant Time Approximation of Parameters of Bounded Degree Graphs.- Sublinear Algorithms in the External Memory Model.- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.- Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability.- Testing Linear-Invariant Non-linear Properties: A Short Report.- Optimal Testing of Reed-Muller Codes.- Query-Efficient Dictatorship Testing with Perfect Completeness.- Composition of Low-Error 2-Query PCPs Using Decodable PCPs.- Hierarchy Theorems for Property Testing.- Algorithmic Aspects of Property Testing in the Dense Graphs Model.- Testing Euclidean Spanners.- Symmetric LDPCCodes and Local Testing.- Some Recent Results on Local Testing of Sparse Linear Codes.- Testing (Subclasses of) Halfspaces.- Dynamic Approximate Vertex Cover and Maximum Matching.- Local Property Reconstruction and Monotonicity.- Green's Conjecture and Testing Linear Invariant Properties.