Implementation Issues in the Fourier Transform Algorithm

作者:Yishay Mansour, Sigal Sahar

摘要

The Fourier transform of Boolean functions has received considerable attention in the last few years in the computational learning theory community, and has come to play an important role in proving many important learnability results. The aim of this work is to demonstrate that the Fourier transform techniques are also a useful and practical algorithm, in addition to having many interesting theoretical properties. In fact, this work was prompted by a genuine problem that was brought to our attention; researchers at a company were trying to come by a method to reverse-engineer a state-free controller. They had the capability of querying the controller on any input, thus setting them in the membership query model, in which the Fourier transform algorithm is set.

论文关键词:computational learning theory, Fourier transform, learning algorithms, implementation issues

论文评审过程:

论文官网地址:https://doi.org/10.1023/A:1011034100370