Coset decision trees and the Fourier algebra

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

Authors: Tom Sanders 

Publication date: 27 January 2022

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

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)).

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

Recommendations

• Bounds in Cohen's idempotent theorem
• Learning Decision Trees Using the Fourier Spectrum
• On the structure of Boolean functions with small spectral norm
• On the structure of Boolean functions with small spectral norm
• scientific article; zbMATH DE number 1200182

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)

Cites Work

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

Cited In (2)

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

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)