Coset decision trees and the Fourier algebra

DOI10.1007/S11854-021-0179-YzbMATH Open1497.43004OpenAlexW4205843339MaRDI QIDQ2073019FDOQ2073019

Authors Tom Sanders

Publication date 27 January 2022

Published in Journal d'Analyse Mathématique (Search for Journal in Brave)

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

zbMATH Keywords

finite groupcoset decision treeFourier algebra norm

Mathematics Subject Classification ID

Arithmetic and combinatorial problems involving abstract finite groups (20D60) Boolean functions (06E30) Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups (43A25)

Abstract: We show that if G is a finite group and f is a {0,1}-valued function on G with Fourier algebra norm at most M then f may be computed by a coset decision tree (that is a decision tree in which at each vertex we query membership of a given coset) having at most exp(exp(exp(O(M^2)))) leaves. A short calculation shows that any {0,1}-valued function which may be computed by a coset decision tree with m leaves has Fourier algebra norm at most exp(O(m)).

Recommendations

• Bounds in Cohen's idempotent theorem
• Learning Decision Trees Using the Fourier Spectrum
• scientific article; zbMATH DE number 1200182

Cites work

• scientific article; zbMATH DE number 1818856 (Why is no real title available?)
• scientific article; zbMATH DE number 3174732 (Why is no real title available?)
• scientific article; zbMATH DE number 44588 (Why is no real title available?)
• scientific article; zbMATH DE number 3391477 (Why is no real title available?)
• A probabilistic technique for finding almost-periods of convolutions
• A quantitative version of the idempotent theorem in harmonic analysis
• A quantitative version of the non-Abelian idempotent theorem
• Additive combinatorics
• Amenability and weak amenability of the Fourier algebra
• Analysis of Boolean Functions
• Arithmetic progressions in sumsets and \(L^p\)-almost-periodicity
• Boolean functions with small spectral norm
• Cohen-Host type idempotent theorems for representations on Banach spaces and applications to Figà-Talamanca-Herz algebras
• Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
• Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
• Ideals with bounded approximate identities in Fourier algebras.
• L'algèbre de Fourier d'un groupe localement compact
• Le théorème des idempotents dans $B(G)$
• Learning Decision Trees Using the Fourier Spectrum
• Mesures ε-idempotentes de norme bornée
• On a Conjecture of Littlewood and Idempotent Measures
• On the Bogolyubov-Ruzsa lemma
• On the Littlewood Problem Modulo a Prime
• On the Wiener norm of subsets of \(\mathbb{Z}_p\) of medium size
• The non-equivalence between the trigonometric system and the system of functions with pointwise restrictions on values in the uniform and L¹ norms
• The structure of approximate groups.

Cited in

(2)

• Learning Decision Trees Using the Fourier Spectrum
• Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time

This page was built for publication: Coset decision trees and the Fourier algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073019)