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

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

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.