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

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

• 批准号: 1409020
• 负责人: J Maurice Rojas
• 金额: $ 25万
• 依托单位: Texas A&M University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1409020&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Sparse; 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.

快速求解方程是使现代技术脱颖而出的：在手机之间传输对话，将数据从太空飞行器发送回地球，导航飞机并使机器人正确移动，所有这些都依赖于求解方程。在每种情况下，方程都有自己的个性 - 我们试图利用的特殊结构，以便更快地找到解决方案。在该项目中，原理研究人员将研究涉及稀疏多项式的方程式 - 多项式的术语很少但程度很高，但求解方程不仅仅是迅速计算，还意味着理解和使用计算硬度。例如，数字理论和代数几何形状的经典结果为我们提供了特殊结构化的方程式，经过数百年的研究，仍然无法迅速解决。这些方程实际上是密码学和复杂性理论中最有用的方程式：可以使用计算硬度来确保敏感数据来确保对手在成功窃取任何东西之前花费大量的努力。但是，真正理解硬度是微妙的：由于错过的理论细节或新发现的后门，每天，代码和密码系统都会被打破。该项目的主要研究人员是代数几何，数字理论，复杂性理论和特殊结构化方程的世界专家。它们带来了复杂的新工具，从未在复杂性理论中使用过，以便更好地分类哪些代数电路定义了棘手的方程式。他们的跨学科方法非常适合吸引数学才华横溢的学生进入理论计算机科学，加密和数理论。