A book: Property Testing

This page is about the book we are currently writing:

Title: Property Testing

Authors: Arnab Bhattacharyya and Yuichi Yoshida

Publisher: Springer

Description:
Property testing aims at designing algorithms that test properties of objects in constant time, independent of the input size. Because of its theoretical importance and practically appealing nature, property testing has been intensively studied in the last couple of decades. The objective of this book is two-fold: The first one is explaining beautiful connections between property testing and other topics in 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 more applied areas such as data mining and databases. As the size of data has rapidly increased in recent times, the classical definition of efficiency as polynomial running time has become outdated. Property testing studies good substitutes 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-freeness
    • Edge-connectivity: connectivity, k-edge-connectivity,
    • Cycle-freeness
    • Minimum spanning trees
    • Vertex cover
    • Bipartiteness
  • 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