Learning Fourier Coefficients: Theory and Application

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Our modern times are characterized by vast amounts of information needed to be stored, searched, encrypted, transmitted, compressed, and so on. The major increase in the amount of data we wish to handle has turned the feasible-but-costly chores of yesterday to infeasible ones, and the feasible chores of yesterday to costly ones. Linear or even sub-linear algorithms are imperative. The stringent complexity requirements imposed by the data explosion phenomena raises new challenges in a large variety of fields and applications. The wide variety of these algorithmic tasks seems to require individual study of the separate challenges, carefully learning the specific properties of each distinct challenge, in a quest for the special angles by which an improved algorithmic respond may be given. A formidable and diverse challenge indeed. Luckily, there are basic algorithmic building blocks that repeatedly emerge in many of the current algorithmic solutions. One of these recurring building blocks is the use of Fourier Transform, and in particular of the Fast Fourier Transform (FFT) algorithm. The FFT algorithm is famous for its efficiency, computing the Fourier Transform of a signal of length $n$ in time $\Theta(n\log n)$. Alas, in the settings of the Data Explosion Era, a super-linear time-complexity often does not suffice. However, examining usages of the FFT algorithm, reveals that in many cases, instead of computing all the entries in the Fourier Transform of a function, it would actually suffice to know only a few "heavy" entries. A task for which sub-linear algorithms have recently be devised. We propose to Explore new input-models for the recent sub-linear algorithms for finding the "heavy" entries of the Fourier transform of functions, which emerge in computer science applications. Improve the time-complexity of the recent sub-linear algorithms for finding the "heavy" entries of the Fourier transform of functions, which emerge in computer science applications. Devise faster algorithms for applications that can benefit from a sub-linear algorithm for finding the "heavy" entries in a Fourier transform. In particular, for application in which the current algorithm uses the FFT algorithm, while it would suffices to find only the "heavy" entries in the Fourier transform. Explore applications of the improved algorithms to questions in complexity theory, cryptography, learning theory, and coding theory. The intellectual merit of the proposed research is that if successful it will have significant impact on our understanding of basic issues in cryptography, coding theory, and complexity theory at large. The impact of speeding up algorithms for data processing tasks would be tremendous. The broader impact of the proposed research will be through the PI's disseminating the knowledge and understanding gained in courses taught at the graduate and undergraduate level on cryptography and algorithms at MIT, as well as in research seminars and conferences nationally and internationally. In addition, the PI and the graduate students working on this research are both women.