课题基金 / 基金详情

Learning Fourier Coefficients: Theory and Application

Learning Fourier Coefficients: Theory and Application
学习傅立叶系数:理论与应用
批准号:
0514167
负责人:
Shafrira Goldwasser
金额:
$20.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2005
资助国家:
美国
项目状态:
已结题
起止时间:
2005-07-01 至 2009-06-30

项目摘要

项目成果

Shafrira Goldwasser的其他基金

相似基金

相关文献

中文摘要
翻译
我们现代的特点是需要存储、搜索、加密、传输、压缩等海量信息。我们希望处理的数据量的大幅增加已经把昨天可行但代价高昂的家务变成了不可行的家务,把昨天可行的家务变成了代价高昂的家务。线性甚至次线性算法势在必行。数据爆炸现象提出的严格的复杂性要求在许多领域和应用中都提出了新的挑战。这些算法任务的种类繁多,似乎需要对不同的挑战进行单独的研究,仔细学习每个不同挑战的具体属性,以寻求给出改进的算法响应的特殊角度。这确实是一项艰巨而多样的挑战。幸运的是,在当前的许多算法解决方案中反复出现了基本的算法构建块。这些反复出现的构件之一是使用傅里叶变换,特别是使用快速傅立叶变换(FFT)算法。FFT算法以其计算长度为$n$的信号在时间$\theta(n\logn)$中的傅里叶变换的效率而闻名。唉,在数据爆炸时代的背景下,超线性的时间复杂性往往是不够的。然而,考察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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Workshops on Geometry of Polynomials
  • 批准号:
    1835986
  • 项目类别:
    Standard Grant
  • 资助金额:
    $6.0万
  • 财政年份:
    2018
  • 负责人:
    Shafrira Goldwasser
  • 依托单位:
EAGER: Holistic Security for Cloud Computing: Computing on Encrypted Data
  • 批准号:
    1347364
  • 项目类别:
    Standard Grant
  • 资助金额:
    $30.0万
  • 财政年份:
    2013
  • 负责人:
    Shafrira Goldwasser
  • 依托单位:
TC: Small: Securing Programs and Data In Remote and Hostile Environments
  • 批准号:
    1018064
  • 项目类别:
    Standard Grant
  • 资助金额:
    $49.92万
  • 财政年份:
    2010
  • 负责人:
    Shafrira Goldwasser
  • 依托单位:
Workshop: Cryptography in the Clouds
  • 批准号:
    0948699
  • 项目类别:
    Standard Grant
  • 资助金额:
    $3.01万
  • 财政年份:
    2009
  • 负责人:
    Shafrira Goldwasser
  • 依托单位:
国内基金
海外基金
Fourier限制性不等式的极值函数存在性
乘性混沌与随机Fourier级数的调和分析
  • 批准号:
    12471145
  • 项目类别:
    面上项目
  • 资助金额:
    43.00万元
  • 批准年份:
    2024
  • 负责人:
    邱彦奇
  • 依托单位:
Moran测度的谱性与Fourier变换的衰减
  • 批准号:
    12401107
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    30.00万元
  • 批准年份:
    2024
  • 负责人:
    刘宗盛
  • 依托单位:
自守L-函数Fourier系数的变号与非零性问题及其应用研究
  • 批准号:
    12401011
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    30.00万元
  • 批准年份:
    2024
  • 负责人:
    华国栋
  • 依托单位: