Implementation Issues in the Fourier Transform Algorithm

Tel-Aviv University Tel-Aviv, ISRAEL Abstract The Fourier transform of boolean functions has come to play an important role in proving many important learnability results. We aim to demonstrate that the Fourier transform techniques are also a useful and practical algorithm in addition to being a powerful theoretical tool. We describe the more prominent changes we have introduced to the algorithm, ones that were crucial and without which the performance of the algorithm would severely deteriorate. Oneof the benefits we present is the confidence level for each prediction which measures the likelihood the prediction is correct. 1 INTRODUCTION It has been used mainly to demonstrate the learnability of various classes of functions with respect to the uniform distribution. The work of [5] developed a very powerful algorithmic procedure: given a function and a threshold parameter it finds in polynomial time all the Fourier coefficients ofthe function larger than the threshold.