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

AF：媒介：协作研究：复杂性和通信中的算术几何方法

基本信息

批准号：
1900881
负责人：
J Maurice Rojas
金额：
$ 30.8万
依托单位：
Texas A&M University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-04-01 至 2023-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1900881&HistoricalAwards=false
关键词：
AF Medium Collaborative Research Arithmetic

项目摘要

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.

安全性和效率仍然是密码和沟通中的核心问题。在过去的几个世纪中，从可以手动打破的临时秘密代码到基于数字理论的方法，即使使用超级计算机对抗对手仍然安全，加密技术已经提高了。随着数字理论的算法提前，我们的保护数据的代码也在效率方面进步：NASA定期使用遥远行星上的地形清晰图片，使用误处理的代码，这些代码通过太阳能，手机和无线电传输的噪声切开。随着我们的沟通方法的发展，我们自然会导致深层数学问题，在我们取得进一步的进展之前，必须解决这些问题。这些问题中的一些也与复杂性理论中的中心问题密切相关。研究人员将专注于解决电路复杂性和伪随机性的中心问题的先进技术。特别是，它们将在算术几何形状上应用最新的进步，以构建新的伪随机发电机和新的复杂性下限。研究人员将追求的一种技术是他们最近发现了一种有效的方法来计算有限环的多项式方程的解决方案。该技术将有助于分析一个新的伪随机发电机家族，其潜在的不可预测性比基于离散对数和保理的早期结构更好。研究团队还将使用从实际和P-ADIC几何形状中的技术来研究结构化多项式的整数解决方案的数量。后一个问题是最近的少数几种方法之一，它有可能产生新的下限，以使电路复杂性以及对PS. NP问题的更好理解。除了这项算法研究外，研究人员还将培训研究生，并利用该项目的所有工作为年轻学生开发新内容和课程和外展计划。调查人员致力于扩大代表性不足的团体参与计算的参与，并确保所有来源的新人才可用于未来的研究。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评估的评估值得支持的。