Introduction to Property Testing

Oded Goldreich

• Publisher: Cambridge University Press
• Year: 2017
• Print ISBN: 9781107194052
• eBook ISBN: 9781108153805
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

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.

Table of contents

• Cover
• Half title
• Title
• Copyright
• Contents
• Preface
• Organization and Chapter Summaries
• Notation
• Acknowledgments
• 1 The Main Themes: Approximate Decision and Sublinear Complexity
• 2 Testing Linearity (Group Homomorphism)
• 3 Low-Degree Tests
• 4 Testing Monotonicity
• 5 Testing Dictatorships, Juntas, and Monomials
• 6 Testing by Implicit Sampling
• 7 Lower Bounds Techniques
• 8 Testing Graph Properties in the Dense Graph Model
• 9 Testing Graph Properties in the Bounded-Degree Graph Model
• 10 Testing Graph Properties in the General Graph Model
• 11 Testing Properties of Distributions
• 12 Ramifications and Related Topics
• 13 Locally Testable Codes and Proofs
• Appendix A: Probabilistic Preliminaries
• Appendix B: A Mini-Compendium of General Results
• Appendix C: An Index of Specific Results
• References
• Index