Property Testing

1. Front Matter

   PDF

2. Editor’s Introduction

   1. A Brief Introduction to Property Testing

      • Oded Goldreich

      Pages 1-5

   2. The Program of the Mini-Workshop

      • Oded Goldreich

      Pages 6-12

3. Surveys

   1. Limitation on the Rate of Families of Locally Testable Codes

      • Eli Ben-Sasson

      Pages 13-31

   2. Testing Juntas: A Brief Survey

      • Eric Blais

      Pages 32-40

   3. Sublinear-time Algorithms

      • Artur Czumaj, Christian Sohler

      Pages 41-64

   4. Short Locally Testable Codes and Proofs: A Survey in Two Parts

      • Oded Goldreich

      Pages 65-104

   5. Introduction to Testing Graph Properties

      • Oded Goldreich

      Pages 105-141

   6. Property Testing of Massively Parametrized Problems – A Survey

      • Ilan Newman

      Pages 142-157

   7. Sublinear Graph Approximation Algorithms

      • Krzysztof Onak

      Pages 158-166

   8. Transitive-Closure Spanners: A Survey

      • Sofya Raskhodnikova

      Pages 167-196

   9. Testing by Implicit Learning: A Brief Survey

      • Rocco A. Servedio

      Pages 197-210

   10. Invariance in Property Testing

       • Madhu Sudan

       Pages 211-227

4. Extended Abstracts

   1. Testing Monotone Continuous Distributions on High-Dimensional Real Cubes

      • Michał Adamaszek, Artur Czumaj, Christian Sohler

      Pages 228-233

   2. On Constant Time Approximation of Parameters of Bounded Degree Graphs

      • Noga Alon

      Pages 234-239

   3. Sublinear Algorithms in the External Memory Model

      • Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

      Pages 240-243

   4. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

      • Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

      Pages 244-252

   5. Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability

      • Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

      Pages 253-259

   6. Testing Linear-Invariant Non-linear Properties: A Short Report

      • Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

      Pages 260-268

   7. Optimal Testing of Reed-Muller Codes

      • Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

      Pages 269-275

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. This state-of-the-art survey presents a collection of extended abstracts and surveys of leading researchers in property testing and related areas; it reflects the program of a mini-workshop on property testing that took place in January 2010 at the Institute for Computer Science (ITCS), Tsinghua University, Beijing, China. The volume contains two editor's introductions, 10 survey papers and 18 extended abstracts.

• VLDB
• algorithms
• clustering
• coding theory
• combinatorics
• complexity
• computational geometry
• computational learning theory
• decision making
• graph theory
• huge data set
• learning
• statistics
• vertex cover
• algorithm analysis and problem complexity

• Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel

  Oded Goldreich

Policies and ethics