Property Testing 2010

Editor's Introduction

• Oded Goldreich:
  A Brief Introduction to Property Testing. 1-5
  
• Oded Goldreich:
  The Program of the Mini-Workshop. 6-12
  

Surveys

• Eli Ben-Sasson:
  Limitation on the Rate of Families of Locally Testable Codes. 13-31
  
• Eric Blais:
  Testing Juntas: A Brief Survey. 32-40
  
• Artur Czumaj, Christian Sohler:
  Sublinear-time Algorithms. 41-64
  
• Oded Goldreich:
  Short Locally Testable Codes and Proofs: A Survey in Two Parts. 65-104
  
• Oded Goldreich:
  Introduction to Testing Graph Properties. 105-141
  
• Ilan Newman:
  Property Testing of Massively Parametrized Problems - A Survey. 142-157
  
• Krzysztof Onak:
  Sublinear Graph Approximation Algorithms. 158-166
  
• Sofya Raskhodnikova:
  Transitive-Closure Spanners: A Survey. 167-196
  
• Rocco A. Servedio:
  Testing by Implicit Learning: A Brief Survey. 197-210
  
• Madhu Sudan:
  Invariance in Property Testing. 211-227
  

Extended Abstracts

• Michal Adamaszek, Artur Czumaj, Christian Sohler:
  Testing Monotone Continuous Distributions on High-Dimensional Real Cubes. 228-233
  
• Noga Alon:
  On Constant Time Approximation of Parameters of Bounded Degree Graphs. 234-239
  
• Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
  Sublinear Algorithms in the External Memory Model. 240-243
  
• Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
  Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. 244-252
  
• Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron:
  Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability. 253-259
  
• Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
  Testing Linear-Invariant Non-linear Properties: A Short Report. 260-268
  
• Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
  Optimal Testing of Reed-Muller Codes. 269-275
  
• Victor Chen:
  Query-Efficient Dictatorship Testing with Perfect Completeness. 276-279
  
• Irit Dinur, Prahladh Harsha:
  Composition of Low-Error 2-Query PCPs Using Decodable PCPs. 280-288
  
• Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
  Hierarchy Theorems for Property Testing. 289-294
  
• Oded Goldreich, Dana Ron:
  Algorithmic Aspects of Property Testing in the Dense Graphs Model. 295-305
  
• Frank Hellweg, Melanie Schmidt, Christian Sohler:
  Testing Euclidean Spanners. 306-311
  
• Tali Kaufman, Avi Wigderson:
  Symmetric LDPC Codes and Local Testing. 312-319
  
• Swastik Kopparty, Shubhangi Saraf:
  Some Recent Results on Local Testing of Sparse Linear Codes. 320-333
  
• Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
  Testing (Subclasses of) Halfspaces. 334-340
  
• Krzysztof Onak, Ronitt Rubinfeld:
  Dynamic Approximate Vertex Cover and Maximum Matching. 341-345
  
• Michael Saks, C. Seshadhri:
  Local Property Reconstruction and Monotonicity. 346-354
  
• Asaf Shapira:
  Green's Conjecture and Testing Linear Invariant Properties. 355-358
  

Last update Fri May 25 08:33:30 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page