Coset decision trees and the Fourier algebra

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

Full description

Saved in:
Bibliographic Details
Published in:Journal d'analyse mathématique (Jerusalem) 2021-12, Vol.144 (1), p.227-259
Main Author: Sanders, Tom
Format: Article
Language:English
Subjects:
Abstract Harmonic Analysis
Algebra
Analysis
Computation
Decision trees
Dynamical Systems and Ergodic Theory
Functional Analysis
Mathematics
Mathematics and Statistics
Partial Differential Equations
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 the 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 )).
ISSN:0021-7670
1565-8538
DOI:10.1007/s11854-021-0179-y