|
" Introduction to property testing / "
Oded Goldreich, Weizmann Institute of Science, Israel.
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
839216
|
| Main Entry
|
:
|
Goldreich, Oded
|
| Title & Author
|
:
|
Introduction to property testing /\ Oded Goldreich, Weizmann Institute of Science, Israel.
|
| Publication Statement
|
:
|
Cambridge, United Kingdom ;New York, NY, USA :: Cambridge University Press,, 2017.
|
|
|
:
|
, ©2017
|
| Page. NO
|
:
|
1 online resource (xxv, 445 pages)
|
| ISBN
|
:
|
1108135250
|
|
|
:
|
: 9781108135252
|
|
|
:
|
1107194059
|
|
|
:
|
9781107194052
|
| Bibliographies/Indexes
|
:
|
Includes bibliographical references and index.
|
| Contents
|
:
|
The main themes: approximate decision and sublinear complexity -- Testing linearity (group homomorphism) -- Low-degree tests -- Testing monotonicity -- Testing dictatorships, juntas, and monomials -- Testing by implicit sampling -- Lower bounds techniques -- Testing graph properties in the dense graph model -- Testing graph properties in the bounded-degree graph models -- Testing graph properties in the general graph model -- Testing properties of distributions -- Ramifications and related topics -- Locally testable codes and proofs.
|
| Abstract
|
:
|
Property testing is concerned with the design of super-fast algorithms for the structural analysis of large quantities of data. The aim is to unveil global features of the data, such as determining whether the data has a particular property or estimating global parameters. Remarkably, it is possible for decisions to be made by accessing only a small portion of the data. Property testing focuses on properties and parameters that go beyond simple statistics. This book provides an extensive and authoritative introduction to property testing. It provides a wide range of algorithmic techniques for the design and analysis of tests for algebraic properties, properties of Boolean functions, graph properties, and properties of distributions.
|
| Subject
|
:
|
Computer algorithms.
|
| Subject
|
:
|
Structural analysis (Engineering)
|
| Subject
|
:
|
Computer algorithms.
|
| Subject
|
:
|
Structural analysis (Engineering)
|
| Dewey Classification
|
:
|
005.1
|
| LC Classification
|
:
|
QA76.9.A43G655 2018
|
| |