Gowers norm, function limits, and parameter estimation

DOI10.1137/1.9781611974331.CH96MaRDI QIDQ4575679zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1410.5053

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05) Polynomials over finite fields (11T06) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: Let $f_i:mathbb{F}_p^{i}o0,1$ be a sequence of functions, where $p$ is a fixed prime and $mathbb{F}_p$ 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.

Recommendations

• Limits of Boolean functions on \(\mathbb{F}_p^n\)
• Correlation testing for affine invariant properties on F _p ⁿ 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

Cited in

(2)

• Semantic limits of dense combinatorial objects
• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time

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)