Coset decision trees and the Fourier algebra (Q2073019)

This paper extends to more general finite groups some results in abelian group theory. The results melt computer science, combinatorics and harmonic analysis (mainly Fourier algebras). Most of them are related to the complexity of the computation of an integer-valued function defined on a finite group. Among other results, we point out the following. The author proves that if a \(\lbrace 0,1\rbrace\)-valued function defined on a finite group is such that its Fourier algebra norm is less than \(M\), then there is a coset decision tree with \(\exp (\exp (\exp (O(M^2))))\) leaves that computes \(f\). Furthermore, the author proves that if \(f\) is an integer-valued function on a finite group with Fourier algebra norm less than \(M\), then \(f\) is a finite combinaison of some integer-valued functions \(z^{(i)}\) related to some subgroups \(K_i\), \(1\le i\le L=O(M)\), with \(\|z^{(i)}\|_{l^1(G/K_i)}\le \exp (\exp (\exp (O(M^2))))\).