Gowers norm, function limits, and parameter estimation
From MaRDI portal
Publication:4575679
DOI10.1137/1.9781611974331.CH96zbMATH Open1411.68179arXiv1410.5053OpenAlexW1607831149MaRDI QIDQ4575679FDOQ4575679
Authors: Yuichi Yoshida 
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Abstract: Let be a sequence of functions, where is a fixed prime and is the finite field of order . 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.
Full work available at URL: https://arxiv.org/abs/1410.5053
Recommendations
- Limits of Boolean functions on \(\mathbb{F}_p^n\)
- Correlation testing for affine invariant properties on F p n in the high error regime
- Correlation testing for affine invariant properties on \(\mathbb{F}_p^n\) in the high error regime
- Large values of the Gowers-Host-Kra seminorms
- On the Gowers norms of certain functions
Randomized algorithms (68W20) Data structures (68P05) Polynomials over finite fields (11T06) Arithmetic combinatorics; higher degree uniformity (11B30)
Cited In (2)
This page was built for publication: Gowers norm, function limits, and parameter estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575679)
