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

点击翻译按钮获取中文摘要

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.