Back to Search
Start Over
Coset decision trees and the Fourier algebra
- Publication Year :
- 2018
-
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)).<br />Comment: 28pp; corrections and typos
- Subjects :
- Mathematics - Classical Analysis and ODEs
Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1805.02168
- Document Type :
- Working Paper