Concept

Property testing

Summary
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure S (such as a graph or a boolean function) satisfies some property P, or is "far" from having this property (meaning an ε-fraction of the representation of S need be modified in order to make S satisfy P), using only a small number of "local" queries to the object. For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ε > 0): :"Given a graph G on n vertices, decide if G is bipartite, or G cannot be made bipartite even after removing an arbitrary subset of at most \epsilon\tbinom n2 edges of G." Property testing algorithms are central to the definition of probabilistically checkable proofs, as a probabilist
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (1)

On Sums of Locally Testable Affine Invariant Properties

Elena Grigorescu, Ghid Maatouk

Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field Fqn to the subfield Fq and include all properties that form an Fq -vector space and are invariant under affine transformations of the domain. Almost all the known locally testable affine-invariant properties have so-called “single-orbit characterizations” — namely they are specified by a single local constraint on the property, and the “orbit” of this constraint, i.e., translations of this constraint induced by affine-invariance. Single-orbit characterizations by a local constraint are also known to imply local testability. In this work we show that properties with single-orbit characterizations are closed under “summation”. To complement this result, we also show that the property of being an n-variate low-degree polynomial over Fq has a single-orbit characterization (even when the domain is viewed as Fqn and so has very few affine transformations). As a consequence we find that the sum of any sparse affine-invariant property (properties satisfied by q O(n)-functions) with the set of degree d multivariate polynomials over Fq has a single-orbit characterization (and is hence locally testable) when q is prime. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties.
Springer2011
Related people

Loading

Related units

No results

Related concepts

No results

Related courses

Loading

Related lectures

Loading