Property Testing : Current Research and Surveys / edited by Oded Goldreich.

Format:

Book

Contributor:

Goldreich, Oded, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 6390.

Theoretical Computer Science and General Issues ; 6390

Language:

English

Subjects (All):

Computer programming.

Algorithms.

Artificial intelligence.

Computer science--Mathematics.

Computer science.

Computers.

Computer graphics.

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Artificial Intelligence.

Discrete Mathematics in Computer Science.

Computation by Abstract Devices.

Computer Graphics.

Local Subjects:

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Artificial Intelligence.

Discrete Mathematics in Computer Science.

Computation by Abstract Devices.

Computer Graphics.

Physical Description:

1 online resource (XI, 359 pages) : 5 illustrations.

Edition:

First edition 2010.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2010.

System Details:

text file PDF

Summary:

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, this approximate decision is made by accessing a small portion of the data set. This state-of-the-art survey presents a collection of extended abstracts and surveys of leading researchers in property testing and related areas; it reflects the program of a mini-workshop on property testing that took place in January 2010 at the Institute for Computer Science (ITCS), Tsinghua University, Beijing, China. The volume contains two editor's introductions, 10 survey papers and 18 extended abstracts.

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.

Other Format:

Printed edition:

ISBN:

978-3-642-16367-8

9783642163678

Access Restriction:

Restricted for use by site license.