NEW BRUNSWICK/PISCATAWAY, N.J. -- Mario Szegedy, associate professor of computer science at Rutgers and a resident of Highland Park, has been named a recipient of the prestigious Gödel Prize for outstanding papers in the area of theoretical computer science, an honor he shares in 2001 with a team of international colleagues.
This year's award ceremony took place July 8 on the Greek island of Crete as a joint event of the International Colloquium on Automata, Languages, and Programming (ICALP) and the Association for Computing Machinery (ACM) Symposium on the Theory of Computing.
Tomasz Imielinski, chair of the department of computer science and director of the Division of Computer and Information Sciences, offered congratulations to Szegedy, saying: "This brings great honor to you and to the department! Your pioneering research efforts demonstrated in the three key papers (see below) recognized by the Gödel Prize serve as a milestone in our understanding of computationally hard problems."
"Tasks ranging from such trivial-looking problems as scheduling, packing, and designing optimum round-trip tours get intractably hard when the number of components get large," explained Szegedy. "The most popular remedy had been to try to solve these problems in an approximate sense, since this would be sufficient for most practical purposes."
In 1991, Szegedy and some of his colleagues proved that one such problem, called Max-Clique, could not have an approximate solution unless it has an exact solution -- a theoretical breakthrough that subsequently led to the findings presented in the prize-winning papers.
Those later publications expanded this notion to an entire class of optimization problems and showed that Max-Clique was not just an exception. The results they presented captured the immediate attention of the computer scientists and further intrigued them with the means by which they were obtained.
"Our intuition came from game theory, and through cryptography -- seemingly unrelated to our studies in combinatorial optimization," said Szegedy. " In fact, several branches of theoretical computer science and mathematics contributed to our work, and made it a very complex theory spanning hundreds of pages. I am delighted the Gödel prize committee awarded us with this high honor while the revolution we started is still rolling on."
Szegedy received a master's degree in mathematics from the University of Budapest, Hungary in 1985, and a doctorate in computer science from the University of Chicago in 1989. After seven years at Bell Laboratories he conducted research at the Institute for Advanced Study, the Princeton-based think tank.
In 2000, Szegedy joined Rutgers as an associate professor in the Faculty of Arts and Sciences-New Brunswick and teaches graduate and undergraduate courses in theoretical computer science.
The Gödel Prize is sponsored jointly by the European Association of Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computing Theory of the New York-based Association for Computing Machinery (ACM-SIGACT).
The prize is named in honor of Czech-American mathematician and logician Kurt Gödel, in recognition of his major contributions to mathematical logic in computer science, physics and philosophy. The prize is accompanied by a $5,000 award. The three papers cited for the Gödel Prize are:
- Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy: "Interactive Proofs and the Hardness of Approximating Cliques." Journal of the ACM, 43 (2):268--292, 1996.
- Sanjeev Arora and Shmuel Safra: "Probabilistic checking of proofs: a New Characterization of NP." Journal of the ACM, 45(1):70-122, 1998.
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and the Hardness of Approximation Problems." Journal of the ACM 45(3): 501-555, 1998.