BIG DATA

Princeton-led group chosen by National Science Foundation to unlock secrets of complex computational problems: The National Science Foundation (NSF) has awarded a $10 million grant for innovative computer science and engineering research to a group of institutions that includes Rutgers University. The grant funds studies into the complexity of certain mathematical and computer science problems, an issue that underpins the security of communications and financial transactions over the Internet. The five-year grant, led by Princeton University, includes investigators at Rutgers, New York University and the Princeton-based Institute for Advanced Study. "Complexity theory is a branch of mathematics that seeks to understand why certain problems are hard to compute," said Eric Allender, professor and chair of computer science in the Rutgers School of Arts and Sciences and one of the university's three investigators on the grant. "We know some problems are difficult, but for many other problems that seem to be hard, we can't rule out the possibility that there is some clever approach that makes them easy to compute." This is an important issue in cryptography – the coding of information to preserve confidentiality – which is based on assumptions that unauthorized decryption is so difficult as to be essentially impossible. "We may believe it's inconceivable that a fast program for one of these problems can be found, but we just can't be certain," he added. "There are no tools that actually prove how hard these are to compute, and that's what we want to create." The researchers claim that a deeper understanding of these issues, known as "intractability," will benefit the physical, biological and social sciences, as many endeavors in those fields incorporate information processing and computational thinking. The grant is part of a new NSF program called Expeditions in Computing, designed to advance research and education in computer and information science and engineering. The Princeton-led team is receiving one of the first four grants awarded under this program, which encourages investigators to form teams across departments and institutions to pursue research that will define the future of computing. "This will give our students the opportunity to be part of a highly demanding and inspiring academic effort," said Mario Szegedy, professor of computer science and the lead investigator at Rutgers. "The collaboration will bring together some of the best minds in the field of computational complexity to stimulate new ideas and approaches to its increasingly difficult questions." A third investigator from Rutgers is Michael Saks, professor of mathematics and director of the university's graduate program in mathematics. The team will also develop instructional materials for high school students and their teachers to advance mathematical education and prepare students to pursue advanced mathematical and computer science studies in universities.