2018/05/06 by Tom Sanders, Sanders, Tom
Mathematics · #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics #math.CA #math.CO
paper · pdf · doi:10.48550/arxiv.1805.02168
28pp; corrections and typos
arxiv created 2019/11/06 · arxiv updated 2019/11/11
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(M2)))) 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)).