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 …

We argue that the symmetries of a property being tested play a central role in property
testing. We support this assertion in the context of algebraic functions, by examining …

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a
verifier that wishes to ascertain the validity of a given statement, using a short (sublinear …

Testing by Implicit Learning: A Brief Survey Page 1 Testing by Implicit Learning: A Brief Survey
Rocco A. Servedio Department of Computer Science Columbia University New York, NY, USA …

We present sublinear‐time (randomized) algorithms for finding simple cycles of length at
least and tree‐minors in bounded‐degree graphs. The complexity of these algorithms is …

We prove a general structural theorem for a wide family of local algorithms, which includes
property testers, local decoders, and probabilistically checkable proofs of proximity. Namely …

A locally decodable code (LDC) C:{0,1\}^k→{0,1\}^n is an error correcting code wherein
individual bits of the message can be recovered by only querying a few bits of a noisy …

Distribution testing is an area of property testing that studies algorithms that receive few
samples from a probability distribution D and decide whether D has a certain property or is …

Abstract Interactive Oracle Proofs (IOP s) are a new type of proof-system that combines key
properties of interactive proofs and PCP s: IOP s enable a verifier to be convinced of the …

Property testing considers the task of testing rapidly (in particular, with very few samples into
the data), if some massive data satisfies some given property, or is far from satisfying the …