Yale Professor wins Godel Prize for showing how computer algorithms solve problems

Aug 13, 2008
Daniel Spielman Presenting Gödel Prize Lecture
Daniel Spielman presenting Gödel Prize lecture. Photo: Donna Marland

Daniel A. Spielman, professor of applied mathematics and computer science at Yale, has been awarded the prestigious Gödel Prize for developing a technique, known as Smoothed Analysis, that helps predict the success of problem-solving with real data and computers. He shared the prize with Shang-Hua Teng, professor of computer science at Boston University.

The award, carrying a $5,000 honorarium, recognizes outstanding papers in theoretical computer science. It was presented to Spielman and Teng by the Special Interest Group on Algorithms and Computing Theory (SIGACT) of the Association for Computing Machinery (ACM) and the European Association for Theoretical Computer Science (EATCS) at the International Colloquium on Automata, Languages, and Programming (ICALP) in Reykjavik, Iceland.

According to the association, this rigorous mathematical analysis provided a giant leap forward for predicting the performance of optimization tools for real data. Understanding the mathematical structure of these problems is necessary for the design of efficient protocols and software. The paper by Spielman and Teng, "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time," was published in the Journal of the Association for Computing Machinery in 2004.

Spielman, a member of the Yale faculty since 2005, previously taught at Massachusetts Institute of Technology (MIT), after completing his postdoctoral work in mathematical sciences at the University of California Berkeley and his PhD at MIT. He graduated summa cum laude with exceptional distinction in computer science from Yale.

Spielman was previously honored with a National Science Foundation Career Award, and an Alfred P. Sloan Foundation Research Fellowship, and his work on Smoothed Analysis was cited by the National Science Foundation as one of three significant accomplishments funded by the computer science division of the NSF in 2003. He also received the celebrated 2002 Information Theory Society Paper Award given by the IEEE Information Theory Society.

Source: Yale University

Explore further: Earthquake simulation tops one quadrillion flops

add to favorites email to friend print save as pdf

Related Stories

What studying networks can tell us about the world

Feb 12, 2014

There was an opening ceremony on Feb. 5 for the Yale Institute for Network Science (YINS), dedicated to exploring fundamental properties of networks as they appear throughout the biological, physical, and ...

Indian researcher helps prove math conjecture from the 1950s

Jul 17, 2013

On June 18, Adam Marcus and Daniel A. Spielman of Yale University, along with Nikhil Srivastava of Microsoft Research India, announced a proof of the Kadison-Singer conjecture, a question about the mathematical foundations ...

Fundamental algorithm gets first improvement in 10 years

Sep 27, 2010

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: First solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple ...

Recommended for you

Tech giants look to skies to spread Internet

2 hours ago

The shortest path to the Internet for some remote corners of the world may be through the skies. That is the message from US tech giants seeking to spread the online gospel to hard-to-reach regions.

Patent talk: Google sharpens contact lens vision

3 hours ago

(Phys.org) —A report from Patent Bolt brings us one step closer to what Google may have in mind in developing smart contact lenses. According to the discussion Google is interested in the concept of contact ...

Wireless industry makes anti-theft commitment

4 hours ago

A trade group for wireless providers said Tuesday that the biggest mobile device manufacturers and carriers will soon put anti-theft tools on the gadgets to try to deter rampant smartphone theft.

Dish Network denies wrongdoing in $2M settlement

13 hours ago

The state attorney general's office says Dish Network Corp. will reimburse Washington state customers about $2 million for what it calls a deceptive surcharge, but the satellite TV provider denies any wrongdoing.

Yahoo sees signs of growth in 'core' (Update)

13 hours ago

Yahoo reported a stronger-than-expected first-quarter profit Tuesday, results hailed by chief executive Marissa Mayer as showing growth in the Web giant's "core" business.

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

superhuman
5 / 5 (1) Aug 13, 2008
I know what he will spend the money on - a laser pointer.

More news stories

Patent talk: Google sharpens contact lens vision

(Phys.org) —A report from Patent Bolt brings us one step closer to what Google may have in mind in developing smart contact lenses. According to the discussion Google is interested in the concept of contact ...

Tech giants look to skies to spread Internet

The shortest path to the Internet for some remote corners of the world may be through the skies. That is the message from US tech giants seeking to spread the online gospel to hard-to-reach regions.

Wireless industry makes anti-theft commitment

A trade group for wireless providers said Tuesday that the biggest mobile device manufacturers and carriers will soon put anti-theft tools on the gadgets to try to deter rampant smartphone theft.

ESO image: A study in scarlet

This new image from ESO's La Silla Observatory in Chile reveals a cloud of hydrogen called Gum 41. In the middle of this little-known nebula, brilliant hot young stars are giving off energetic radiation that ...

First direct observations of excitons in motion achieved

A quasiparticle called an exciton—responsible for the transfer of energy within devices such as solar cells, LEDs, and semiconductor circuits—has been understood theoretically for decades. But exciton movement within ...

Warm US West, cold East: A 4,000-year pattern

Last winter's curvy jet stream pattern brought mild temperatures to western North America and harsh cold to the East. A University of Utah-led study shows that pattern became more pronounced 4,000 years ago, ...