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.