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...

Full description

Bibliographic Details
Corporate Author: SpringerLink (Online service)
Other Authors: Goldreich, Oded. (Editor)
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.