New National Science Foundation Grants to Support Fundamental Research on Theoretical Computer Science
The National Science Foundation (NSF) has awarded a $10 million Expeditions in Computing grant to a team of researchers in order to advance research and education in the study of computational intractability. The grant will be shared by the Institute for Advanced Study, Princeton University, New York University and Rutgers, The State University of New Jersey. The Institute's participation will be led by Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics, and Russell Impagliazzo, Visiting Professor in the School.
The Institute has also received an NSF grant of $1.75 million for a project entitled "CDI Type II: Pseudorandomness," directed by Jean Bourgain, Russell Impagliazzo, Peter Sarnak and Avi Wigderson of the Institute's School of Mathematics. The grant is part of Cyber-Enabled Discovery and Innovation (CDI), NSF's bold five-year initiative to create revolutionary science and engineering research via computational thinking.
Funds from these two grants will support five postdoctoral Members and more senior Visitors in the school, working on the mathematics of computation.
"The areas of computational intractability and pseudorandomness have been among the most exciting scientific disciplines in the past decade, with remarkable achievements and challenges for the future," said Wigderson. "We are excited about the two new initiatives at the National Science Foundation, and that the Institute's excellence in these areas of research was recognized by these awards. The funds and collaborations will allow us to focus more effort into these fundamental problems."
The Expeditions in Computing "intractability" grant will enable collaborators at Princeton, Rutgers, NYU and the Institute to attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The investigators hope to gain a better understanding of the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics.
The investigators working on the CDI "pseudorandomness" grant aim to transform research in mathematics and computer science by bringing together two major research tracks that have been progressing in parallel. In many areas of mathematics, including analysis, number theory, ergodic theory and combinatorics, a central question is: What random-like properties does a (deterministic) mathematical structure have? In many areas of computer science, including network theory, error correction, computational complexity and derandomization, a major question is: Can we deterministically and efficiently design objects with specific random-like properties? The investigators intend to view both analytic (mathematical) and synthetic (computer science) approaches to gain a better understanding of the same fundamental pseudorandomness phenomena and its interaction with structure.
About the Institute for Advanced Study
The Institute for Advanced Study is one of the world’s leading centers for theoretical research and intellectual inquiry. The Institute exists to encourage and support curiosity-driven research in the sciences and humanities—the original, often speculative thinking that produces advances in knowledge that change the way we understand the world. Work at the Institute takes place in four Schools: Historical Studies, Mathematics, Natural Sciences and Social Science. It provides for the mentoring of scholars by a permanent Faculty of approximately 30, and it ensures the freedom to undertake research that will make significant contributions in any of the broad range of fields in the sciences and humanities studied at the Institute.
The Institute, founded in 1930, is a private, independent academic institution located in Princeton, New Jersey. Its more than 6,000 former Members hold positions of intellectual and scientific leadership throughout the academic world. Thirty-three Nobel Laureates and 40 out of 56 Fields Medalists, as well as many winners of the Wolf and MacArthur prizes, have been affiliated with the Institute.