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

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

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.