Learning Fourier Coefficients: Theory and Application

现代社会的特点是需要存储、搜索、加密、传输、压缩等大量信息，我们希望处理的数据量的大幅增加，使昨天可行但昂贵的工作变得不可行，昨天可行的工作变得昂贵。 线性甚至次线性算法是必不可少的。数据爆炸现象所带来的严格的复杂性要求在许多领域和应用中提出了新的挑战。这些算法任务的种类繁多，似乎需要对单独的挑战进行单独的研究，仔细学习每个不同挑战的特定属性，以寻求可以给出改进的算法响应的特殊角度。这确实是一个艰巨而多样的挑战。幸运的是，在当前的许多算法解决方案中，有一些基本的算法构建块反复出现。这些反复出现的构建块之一是使用傅立叶变换，特别是快速傅立叶变换（FFT）算法。 FFT算法以其效率而闻名，计算长度为$n$的信号在时间$\Theta（n\log n）$上的傅立叶变换。唉，在数据爆炸时代的背景下，超线性的时间复杂度往往是不够的。然而，检查FFT算法的使用，揭示了在许多情况下，而不是计算函数的傅里叶变换中的所有条目，实际上只需要知道一些“重”条目就足够了。本文提出了一种新的输入模型，用于研究在计算机科学应用中出现的求函数傅立叶变换的“重”项的次线性算法，改进了求函数傅立叶变换的“重”项的次线性算法的时间复杂度，并提出了一种新的输入模型。为应用程序设计更快的算法，这些应用程序可以从用于查找傅立叶变换中的“重”项的次线性算法中受益。特别是，对于当前算法使用FFT算法的应用，而仅找到傅立叶变换中的“重”项就足够了。探索改进算法在复杂性理论、密码学、学习理论和编码理论中的应用。所提出的研究的智力价值是，如果成功，它将对我们理解密码学中的基本问题产生重大影响，编码理论和复杂性理论 加速算法对数据处理任务的影响将是巨大的。拟议研究的更广泛影响将通过PI传播在麻省理工学院研究生和本科生阶段教授的密码学和算法课程中获得的知识和理解，以及在国内和国际上的研究研讨会和会议。此外，PI和从事这项研究的研究生都是女性。

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 costlyones. Linear or even sub-linear algorithms are imperative. The stringent complexityrequirements 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 thisresearch are both women.