ACM SIGACT Honors Research Team for Helping Computers Solve Practical Problems

 

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

Richard Ladner				Virginia Gold
ACM SIGACT Chair				ACM
206-543-9347				212-626-0505
[email protected]				[email protected]

 

NEW YORK, May 28, 2008 – ACM's Special Interest Group on Algorithms and Computing Theory (SIGACT) has recognized the contribution of Daniel A. Spielman and Shang-Hua Teng for developing a rigorous framework to explain the practical success of algorithms on real data and real computers that could not be clearly understood through traditional techniques. Their technique, know as Smoothed Analysis, relies on deep mathematical analysis and insight. Since its appearance in 2001, it has been used as a basis for considerable research, confirming its importance to scientific computing. SIGACT and the European Association for Theoretical Computer Science (EATCS) will present the 2008 Gödel Prize for outstanding papers in theoretical computer science to Spielman and Teng at the International Colloquium on Automata, Languages, and Programming (ICALP) July 6 to 13, in Reykjavik, Iceland.

In a paper titled "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time," the authors address a fundamental question of how algorithms function. Their research explains why the Simplex Algorithm, an important tool used by computers to solve a broad, basic class of optimization problems, works effectively in many practical areas, especially in business. It also represents a huge advance in addressing the grand challenge of predicting the performance of algorithms, which are clearly specified procedures guaranteed to give the correct answer, and heuristics, which are methods of solving problems through intelligent trial and error.

Understanding the mathematical structure of these problems is necessary to designing efficient algorithms and software. The findings of Spielman and Teng were published in the Journal of the ACM in 2004.

Daniel Spielman, professor of applied mathematics and computer science at Yale University, previously taught at Massachusetts Institute of Technology (MIT), and completed his postdoctoral work in mathematical sciences at the University of California Berkeley. He was awarded the ACM Doctoral Dissertation Award in 1995, and was honored with the Best Student Paper award at the ACM Symposium on Theory of Computing in both 1994 and 1995. A graduate of Yale with a BA degree and the winner of the Beckwith Prize in mathematics, Spielman received a Ph.D. degree in mathematics from MIT.

Shang-Hua Teng is a professor of computer science at Boston University and senior research scientist at Akamai Technologies, Inc. He is also visiting professor at Tsinghua University in Beijing, China, visiting professor at Microsoft Research Asia, and affiliated research professor of mathematics at MIT. Prior to joining Boston University, he was associate professor at the University of Illinois at Urbana-Champaign; assistant professor of computer science at the University of Minnesota; and instructor of mathematics at MIT. He obtained a postdoctoral position at Xerox Palo Alto Research Center (PARC) where he began an active participation with industry and collaboration with engineers and scientists in developing real-world products. Teng received dual B.S. degrees in computer science and electrical engineering from Shanghai Jiao-Tong University, and an MS degree in computer science from the University of Southern California. He was awarded a Ph.D. degree in computer science from Carnegie Mellon University.

The Gödel Prize, which includes an award of $5,000, is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20^th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.

 

About ACM

ACM, the Association for Computing Machinery www.acm.org, is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.

 

About SIGACT

The ACM Special Interest Group on Algorithms and Computation Theory http://sigact.acm.org fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

About EATCS

The European Association for Theoretical Computer Science http://eatcs.org is an international organization aimed at promoting research in the wide field of the foundations of computer science (ranging from formal languages, abstract computation models, algorithm design and complexity analysis, to applications of logic and semantics in programming). It facilitates the exchange of ideas and results among computer scientists, in particular through the organization of the annual International Conference on Automata, Languages and Programming (ICALP).