Testing linear-invariant non-linear properties: A short report Conference

Bhattacharyya, A, Chen, V, Sudan, M et al. (2010). Testing linear-invariant non-linear properties: A short report . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 6390 LNCS 260-268. 10.1007/978-3-642-16367-8_18

cited authors

  • Bhattacharyya, A; Chen, V; Sudan, M; Xie, N

authors

abstract

  • The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied by a property and its testability. Particularly, they studied properties that were invariant under linear transformations of the domain and gave a characterization of testability in certain settings. However, the properties that they examined were also linear. This led us to investigate linear-invariant properties that are not necessarily linear. Here we describe some of the resulting works which consider natural linear-invariant properties, specifically properties that are described by forbidden patterns of values that a function can take, and show testability under various settings. © 2010 Springer-Verlag.

publication date

  • November 24, 2010

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 10

International Standard Book Number (ISBN) 13

start page

  • 260

end page

  • 268

volume

  • 6390 LNCS