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

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

• 批准号: 1247081
• 负责人: Cristopher Moore
• 金额: $ 21.77万
• 依托单位: Santa Fe Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-05-12 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1247081&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 密码系统，即使量子计算机建成后，是否仍然安全。因此，他们的研究对算法、安全和密码学具有重要影响。他们教授的课程旨在培训物理和计算机科学的学生在这些学科之间的边界工作，他们的外展活动包括将这些材料带给高中和初中教师。