AF: Medium: Collaborative Research: Arithmetic Geometry Methods in Complexity and Communication

安全性和效率一直是密码学和通信领域的核心问题。几个世纪以来，密码学已经取得了进步，从可以用手破解的临时密码，到基于数论的方法，即使面对使用超级计算机的对手，这些方法仍然是安全的。随着数论算法的进步，我们保护数据的代码也在效率上取得了进步：美国国家航空航天局（NASA）定期传输遥远星球上清晰的地形图像，使用的纠错代码可以消除太阳耀斑、手机和无线电传输的噪音。随着我们的交流方式的发展，我们自然会遇到一些深奥的数学问题，这些问题必须先解决，才能取得进一步的进展。其中一些问题也与复杂性理论的核心问题和优化的新进展密切相关。研究人员将专注于解决电路复杂性和伪随机性等核心问题的先进技术。特别是，他们将应用算术几何的最新进展来构建新的伪随机生成器和新的复杂性下界。研究人员将追求的一项技术是他们最近发现的一种有效的方法来计算有限环上多项式方程的解。这种技术将有助于分析一组新的伪随机生成器，它们比以前基于离散对数和因式分解的构造具有更好的不可预测性。研究小组还将使用实几何和p进几何的技术来研究结构多项式的整数解的数量。后一个问题是最近几种有可能产生新的电路复杂度下限和更好地理解P与NP问题的方法之一。除了算法研究之外，研究人员还将培训研究生，并利用该项目的所有工作为年轻学生开发新的课程内容和外展计划。研究人员致力于扩大未被充分代表的群体在计算机领域的参与，并确保来自所有来源的新人才可用于未来的研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Security and efficiency remain central problems in cryptology and communication. Over the centuries, cryptography has advanced, from ad hoc secret codes that can be broken by hand, to methods based on number theory which remain secure even against adversaries using super-computers. As algorithms from number theory have advanced, our codes for protecting data have also progressed in efficiency: NASA regularly transmits clear pictures of terrain on faraway planets, using error-correcting codes that cut through the noise of solar flares, cell phones, and radio transmissions. As our communication methods have evolved, we are naturally led to deep mathematical problems which must be solved before we can make further progress. Some of these problems are also deeply connected to central questions in complexity theory and new advances in optimization.The investigators will focus on advanced techniques toward tackling central problems in circuit complexity and pseudo-randomness. In particular, they will apply recent advances in arithmetic geometry to the construction of new pseudo-random generators and new complexity lower bounds. One technique the investigators will pursue is their recent discovery of an efficient method to count solutions of polynomial equations over finite rings. This technique will help analyze a new family of pseudo-random generators with potentially better unpredictability than earlier constructions based on discrete logarithms and factoring. The research team will also use techniques from real and p-adic geometry to study the number of integer solutions to structured polynomials. The latter problem is one of the few recent methods with the potential to yield new lower bounds for circuit complexity and a better understanding of the P vs. NP question. In addition to this algorithmic research, the investigators will train graduate students, and use all work from this project to develop new content for courses and outreach programs for younger students. The investigators are committed to broadening the participation of under-represented groups in computing and ensuring new talent from all sources is available for future research.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.