Property Testing

This book introduces important results and techniques in property testing, where the goal is to design algorithms that decide whether their input satisfies a predetermined property in sublinear time, or even in constant time – that is, time is independent of the input size. 

This book consists of three parts. The first part provides an introduction to the foundations of property testing. The second...