2014/10/19 by Yuichi Yoshida, Yoshida, Yuichi · 1 citation
Computer Science · Mathematics · #Affine transformation #Characterization (materials science) #Combinatorics #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Computer science #Constant (computer programming) #Constant function #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Invariant (physics) #Limit (mathematics) #Mathematical Dynamics and Fractals #Mathematical analysis #Mathematics #Norm (philosophy) #Numerical Methods and Algorithms #Physics #Property testing #Pure mathematics #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1410.5053
published in arXiv (Cornell University) (Cornell University) · arXiv admin note: text overlap with arXiv:1212.3849, arXiv:1308.4108 by other authors
openalex publication_date 2014/10/19 · arxiv created 2015/03/26 · arxiv updated 2015/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \fi:\mathbbFpi → \0,1\\ be a sequence of functions, where p is a fixed prime and \mathbbFp is the finite field of order p. The limit of the sequence can be syntactically defined using the notion of ultralimit. Inspired by the Gowers norm, we introduce a metric over limits of function sequences, and study properties of it. One application of this metric is that it provides a characterization of affine-invariant parameters of functions that are constant-query estimable. Using this characterization, we show that the property of being a function of a constant number of low-degree polynomials and a constant number of factored polynomials (of arbitrary degrees) is constant-query testable if it is closed under blowing-up. Examples of this property include the property of having a constant spectral norm and degree-structural properties with rank conditions.