Property Testing Current Research and Surveys /
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, th...
Corporate Author: | |
---|---|
Other Authors: | |
Format: | Electronic |
Language: | English |
Published: |
Berlin, Heidelberg :
Springer Berlin Heidelberg,
2010.
|
Series: | Lecture Notes in Computer Science,
6390 |
Subjects: | |
Online Access: | View fulltext via EzAccess |
Table of Contents:
- 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.