AF: Small: Collaborative Research: Representation-theoretic techniques for pseudorandomness and lower bounds

AF：小：协作研究：伪随机性和下界的表示理论技术

• 批准号: 1117426
• 负责人: Cristopher Moore
• 金额: $ 24.1万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-05-15 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117426&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Representation

Fourier analysis, where we decompose a complex function into a sum of simple oscillations, is used in virtually every form of digital technology, from JPEG compression to voice recognition. In computer science, Fourier analysis has led to new algorithms for "pseudorandom numbers," i.e., numbers with no apparent pattern, which are useful both in cryptography and in algorithms for estimating functions and confirming computational claims. Fourier analysis also plays a key role in Shor's quantum algorithm for factoring, which breaks RSA public-key cryptography, and in proofs that some problems are hard to solve with certain kinds of parallel algorithms or circuits. Profs. Moore and Russell will use the more powerful tool of nonabelian Fourier analysis to obtain new results in these areas. In particular, they propose new ways to "derandomize" algorithms, replacing random numbers with pseudorandom ones. They will study the extent to which rich, high-dimensional structures can be embedded in low-dimensional spaces with only a small amount of distortion, and prove that certain problems require a long time even for quantum computers to solve. Finally, they will study whether some alternatives to RSA, such as the McEliece cryptosystem based on error-correcting codes, will remain secure even if and when quantum computers are built. Thus their research has important impacts on algorithms, security, and cryptography. They teach courses that train students from Physics and Computer Science to work at the boundary between these disciplines, and their outreach activities include bringing this material to high school and middle-school teachers.

傅立叶分析，我们把一个复杂的函数分解成一个简单的振荡的总和，几乎被用于每一种形式的数字技术，从JPEG压缩到语音识别。在计算机科学中，傅立叶分析导致了“伪随机数”的新算法，即，数字没有明显的模式，这是有用的密码学和算法，估计功能和确认计算索赔。傅立叶分析在Shor的量子分解算法中也扮演了关键角色，它打破了RSA公钥密码学，并证明了某些问题很难用某些类型的并行算法或电路来解决。教授摩尔和罗素将使用更强大的工具，非阿贝尔傅立叶分析，以获得新的结果，在这些领域。特别是，他们提出了新的方法来“去随机化”算法，用伪随机数取代随机数。他们将研究丰富的高维结构在多大程度上可以嵌入低维空间，只有少量的扭曲，并证明某些问题甚至需要量子计算机解决很长时间。最后，他们将研究RSA的一些替代方案，例如基于纠错码的McEliece密码系统，即使在量子计算机建成时也将保持安全。因此，他们的研究对算法，安全和密码学有重要影响。他们教授培训物理和计算机科学学生在这些学科之间的边界工作的课程，他们的推广活动包括将这些材料带给高中和中学教师。