Implementation issues in the Fourier transform algorithm

The Fourier transform of Boolean functions has received considerable attent ion in the last few years in the computational learning theory community, a nd has come to play an important role in proving many important learnabilit y results. The aim of this work is to demonstrate that the Fourier transfor m techniques are also a useful and practical algorithm, in addition to havi ng many interesting theoretical properties. In fact, this work was prompted by a genuine problem that was brought to our attention; researchers at a c ompany were trying to come by a method to reverse-engineer a state-free con troller. They had the capability of querying the controller on any input, t hus setting them in the membership query model, in which the Fourier transf orm algorithm is set. In order to keep the algorithm run-time reasonable and still produce accura te hypotheses, we had to perform many optimizations. In the paper we discus s the more prominent optimizations, ones that were crucial and without whic h the performance of the algorithm would severely deteriorate. One of the b enefits we present is the confidence level the algorithm produces in additi on to the predictions. The confidence level measures the likelihood that th e prediction is correct.