Property Testing Current Research and Surveys /

• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Άλλοι συγγραφείς: Goldreich, Oded (Επιμελητής έκδοσης)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2010.
• Σειρά: Lecture Notes in Computer Science, 6390
• Θέματα: Computer science.; Computer programming.; Computers.; Algorithms.; Computer science > Mathematics.; Artificial intelligence.; Computer graphics.; Computer Science.; Programming Techniques.; Algorithm Analysis and Problem Complexity.; Artificial Intelligence (incl. Robotics).; Discrete Mathematics in Computer Science.; Computation by Abstract Devices.; Computer Graphics.

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

Πίνακας περιεχομένων:

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