Property Testing 2010
Oded Goldreich (Ed.): Property Testing - Current Research and Surveys [outgrow of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010]. Springer 2010 Lecture Notes in Computer Science ISBN 978-3-642-16366-1
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
- 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
- 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
- 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
- Asaf Shapira: Green's Conjecture and Testing Linear Invariant Properties. 355-358
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team