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

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

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.