default search action
Property Testing 2010
- Oded Goldreich:
Property Testing - Current Research and Surveys. Lecture Notes in Computer Science 6390, Springer 2010, 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 - 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 E. Saks, C. Seshadhri:
Local Property Reconstruction and Monotonicity. 346-354 - Asaf Shapira:
Green's Conjecture and Testing Linear Invariant Properties. 355-358
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.