INSTITUTE FOR ADVANCED STUDY RECEIVES GRANT TO STUDY COMPUTATIONAL COMPLEXITY THEORY

PRINCETON, N.J. - March 25, 2004 - The Institute for Advanced Study has received a grant from the National Science Foundation to support a combination of research and educational objectives relating to Computational Complexity Theory. Principal Investigators for the project are Avi Wigderson, who is Herbert H. Maass Professor in the School of Mathematics, and Alexander Razborov, a member in the School of Mathematics. 

The $283,751 award for 2003-04 is the first segment of a $1,500,000 continuing grant. It is designed to facilitate the presence of permanent (as well as long- and short-term) researchers in the School of Mathematics, and to encourage interaction among mathematical scientists. The grant will also support several seminar series. 

Wigderson and Razborov propose research on fundamental problems of computational complexity theory, with special focus on the interactions among them. They will concentrate on the power of randomness in computation, the complexity of proofs and search for proofs, and the power and limitations of various computational models.

"Computational complexity research here at the Institute for Advanced Study is guided by a few clear questions, deeply motivated by scientific, practical, and philosophical concerns," notes Wigderson. "We examine such questions as: Are there natural computationally difficult problems? What characterizes a theorem that is difficult to prove? Does randomization help computation?"

"We are extremely grateful to the National Science Foundation for supporting our research in this exciting field." 

Razborov, winner of the 1990 Rolf Nevanlinna Prize of the International Mathematical Union, studies combinatorics, theoretical computer science, and complexity theory. He graduated from Moscow University and received his Ph.D. from the Steklov Mathematical Institute in Moscow, where he is a principal researcher.

Wigderson’s research interests are in complexity theory, algorithms, randomness, and cryptography. A graduate of the Technion, Haifa, Israel, he earned his Ph.D. from Princeton University. Wigderson, who heads the Institute’s program for theoretical computing and discrete mathematics, won the 1994 Nevanlinna Prize. He has been on the faculty of the Institute for Advanced Study since 1999.