Property Testing

by Arnab Bhattacharyya and Yuichi Yoshida

This page is about the book we are currently writing, which will be published from Springer.

Property testing aims at designing algorithms that test properties of objects in constant time, which is independent of the input size. Because of its theoretical importance and practically appealing nature, property testing has been intensively studied in the last decades. The objective of this book is two-fold: The first one is explaining beautiful connections between property testing and other discrete mathematics such as graph theory and harmonic analysis. Property testing not only uses analytical tools from those areas but also has contributed to deepen them. The other one is explaining basic results in property testing in an accessible form to people in practical areas such as data mining and database. As the sizes of data have been rapidly increased in the age of big data, even polynomial-time algorithms are too slow to handle them. Property testing will be a good substitute to handle such large data.

The topics covered will include:

• Testing Basic Properties
  • Strings: Palindromes, Dyck Language
  • Graph properties in the adjacency matrix model
    • Partition properties: biblique, bipartiteness, general partition property.
    • Subgraph freeness: square-freeness, triangle-freeness, H-freeness.
  • Graph properties in the bounded-degree model
    • H-freenes
    • Connectivity properties
    • Cycle-freeness
    • Minimum spanning trees
    • Bipartiteness
    • Maximum Matching
  • Functions
    • Introduction to Fourier analysis
    • Monotonicity, Juntas, Linearity, Low-degree polynomials
    • Locally testable codes
• Lower bound techniques
  • Yao’s minimax lemma
  • Communication complexity
• Testing advanced properties
  • Strings: Regular language
  • Graph properties in the adjacency matrix model
    • Induced H-freeness
    • Hereditary properties
    • Regular-reducible properties
  • Graph properties in the bounded-degree model
    • (k, l)-fullness
    • Minor-closed properties
  • Functions
    • Introduction to higher-order Fourier analysis
    • Locally characterized properties
    • Regular-reducible properties

• Other topics