权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

项目摘要

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.

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