Property Testing: Current Research and Surveys

ISBN-13: 9783642163661 / Angielski / Miękka / 2010 / 359 str.

Oded Goldreich

Opis

Property Testing is the study of super-fast algorithms for approximate decision making. This volume features work presented at a mini-workshop on property testing that took place January 2010 at the Institute for Computer Science, Tsinghua University, China.

Spis treści

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.