Journal article icon

Journal article

Coset decision trees and the Fourier algebra

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 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(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)).
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1007/s11854-021-0179-y

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
St Hugh's College
Role:
Author
ORCID:
0000-0003-1809-8248
Publisher:
Springer
Journal:
Journal d'Analyse Mathematique More from this journal
Volume:
144
Pages:
227-259
Publication date:
2021-12-14
Acceptance date:
2019-11-17
DOI:
EISSN:
1565-8538
ISSN:
0021-7670
Language:
English
Keywords:
Pubs id:
pubs:905457
UUID:
uuid:4adeec12-6c2a-4d95-b233-7194eb8ec2ad
Local pid:
pubs:905457
Source identifiers:
905457
Deposit date:
2019-12-03

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP