NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:8659
Title:Efficiently Learning Fourier Sparse Set Functions

The main contribution of this paper is an information theoretically optimal algorithm (in terms of the number of queries it makes to the function) for learning a sparse fourier approximation. This is a well-studied problem that is at the heart of many applications in property testing. The reviewers all felt that the problem is important and the techniques are clever and were enthusiastic about this paper.