AF: Medium: Collaborative Research: Sparse Polynomials, Complexity, and Algorithms

AF：媒介：协作研究：稀疏多项式、复杂性和算法

• 批准号: 1407623
• 负责人: Shuhong Gao
• 金额: $ 25.36万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1407623&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Sparse

Solving equations quickly is what gets modern technology off the ground: Transmitting conversations between cellphones, sending data from space-craft back to earth, navigating aircraft, and making robots move correctly, all rely on solving equations quickly. In each setting, the equations have their own personality -- a special structure that we try to take advantage of, in order to find solutions more quickly. In this project, the principle investigators will study equations involving sparse polynomials -- polynomials that have few terms but very high degree.But solving equations is more than just calculating quickly -- it also means understanding, and using, computational hardness. For example, classical results in Number Theory and Algebraic Geometry give us specially structured equations that, after centuries of research, still can not be solved quickly. These are the equations that are actually the most useful in Cryptography and complexity theory: Computational hardness can be used to secure sensitive data by forcing an adversary to spend a prohibitively large effort before successfully stealing anything. However, truly understanding hardness is subtle: Every day, codes and cryptosystems are broken because of a missed theoretical detail or a newly discovered backdoor.The principal investigators on this project are world experts in Algebraic Geometry, Number Theory, Complexity Theory, and specially structured equations. They bring sophisticated new tools, never used before in Complexity Theory, in order to better classify what kinds of algebraic circuits define intractable equations. Their interdisciplinary approach is well-suited toward attracting mathematically talented students to theoretical Computer Science, Cryptography, and Number Theory.

快速求解方程是现代技术的成功之处：在手机之间传输对话，从宇宙飞船上发送数据回地球，驾驶飞机，让机器人正确移动，所有这些都依赖于快速求解方程。在每种情况下，方程式都有自己的个性--我们试图利用一种特殊的结构，以便更快地找到答案。在这个项目中，原理研究人员将研究涉及稀疏多项式的方程--项少但次数很高的多项式。但求解方程不仅仅是快速计算--它还意味着理解和使用计算难度。例如，数论和代数几何中的经典结果给了我们特殊的结构方程，经过几个世纪的研究，仍然不能快速求解。这些公式在密码学和复杂性理论中实际上是最有用的：计算难度可以用来保护敏感数据，方法是迫使对手在成功窃取任何东西之前花费令人望而却步的巨大努力。然而，真正理解困难是微妙的：每天，代码和密码系统都会因为错过理论细节或新发现的后门而崩溃。这个项目的主要研究人员是代数几何、数论、复杂性理论和特殊结构方程的世界专家。它们带来了复杂的新工具，以前从未在复杂性理论中使用过，以便更好地对定义难解方程的代数电路进行分类。他们的跨学科方法非常适合于吸引有数学天赋的学生学习理论计算机科学、密码学和数论。