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

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

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.