**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# On Sums of Locally Testable Affine Invariant Properties

Abstract

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.

Official source

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 concepts (44)

Related MOOCs (11)

Affine transformation

In Euclidean geometry, an affine transformation or affinity (from the Latin, affinis, "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generally, an affine transformation is an automorphism of an affine space (Euclidean spaces are specific affine spaces), that is, a function which maps an affine space onto itself while preserving both the dimension of any affine subspaces (meaning that it sends points to points, lines to lines, planes to planes, and so on) and the ratios of the lengths of parallel line segments.

Affine space

In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments. In an affine space, there is no distinguished point that serves as an origin. Hence, no vector has a fixed origin and no vector can be uniquely associated to a point.

Affine shape adaptation

Affine shape adaptation is a methodology for iteratively adapting the shape of the smoothing kernels in an affine group of smoothing kernels to the local image structure in neighbourhood region of a specific image point. Equivalently, affine shape adaptation can be accomplished by iteratively warping a local image patch with affine transformations while applying a rotationally symmetric filter to the warped image patches. Provided that this iterative process converges, the resulting fixed point will be affine invariant.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Related publications (48)

Annalisa Buffa, Pablo Antolin Sanchez, Margarita Chasapi

This contribution presents a model order reduction framework for real-time efficient solution of trimmed, multi-patch isogeometric Kirchhoff-Love shells. In several scenarios, such as design and shape optimization, multiple simulations need to be performed ...

2023We prove a conjecture of Lecouvey, which proposes a closed, positive combinatorial formula for symplectic Kostka-Foulkes polynomials, in the case of rows of arbitrary weight. To show this, we construct a new algorithm for computing cocyclage in terms of wh ...

In a number of cases the minimal polynomials of the images of unipotent elements of non-prime order in irreducible representations of the exceptional algebraic groups in good characteristics are found. It is proved that if p > 5 for a group of type E-8 and ...

2019