CMU professor honored for computational complexity breakthrough

Steven Rudich, professor of computer science at Carnegie Mellon, and Alexander A. Razborov, a mathematician and computational theorist at the Steklov Mathematical Institute in Moscow, will receive the $5,000 prize at the ACM Symposium on Theory of Computing, June 11–13 in San Diego.

The ACM's Special Interest Group on Algorithms and Computing Theory recognized Rudich and Razborov for their work on the P vs. NP problem, a classic question concerning computational complexity that underlies the security of ATM cards, computer passwords and electronic commerce. It is literally a million-dollar question — one of seven Millennium Problems that the Clay Mathematics Institute has offered $1 million for solving.

The Gödel prize is named for Kurt Gödel (1906–1978), an Austrian-American mathematician and philosopher who had a major impact on the foundations of computer science and was among the first to puzzle over the P vs. NP problem.

"Of all of the prizes I could win, I would choose this one," Rudich said. "Gödel has been my luminary hero since I was 12."

The P vs. NP question asks whether the class of problems with solutions that can be quickly recognized (complexity class NP) is the same as the class of problems with solutions that can be quickly generated (complexity class P). In human experience, it is intuitive that the ability to recognize something (like a good musical piece) is easy compared to being able to generate one yourself (like a good composer). People strongly suspect, based on a shared awe of creativity, that NP is a larger class than P. Cryptographers hope that is so; the security of all digital cryptographic systems requires it. At the same time, other computer scientists hope for the exact opposite — they hope to find unexpected shortcuts in the efficiency of creative problem-solving. To date, no one has formulated a mathematical proof that can answer the question one way or the other.

Findings by Rudich and Razborov brought decades of work to find such a proof to a screeching halt. In a paper presented at the Symposium on Theory of Computing in 1994 and published in 1997 in the Journal of Computer and System Sciences, they showed that a wide class of proof techniques they call "natural proofs" can't solve the P vs. NP question. What's more, they found that those previous results turned out to have an almost contradictory double life, providing methods for breaking a wide class of cryptosystems.

That's not to say that a mathematical proof for P vs. NP is impossible, Rudich said, but it will have to be very different from the natural proofs that mathematicians had been employing.

To date, no one has convincingly devised such a proof, but Rudich is among those who are trying. "I've devoted my life to this question," he said. And if he can't solve it, he's convinced someone will. "I'm a big believer in human creativity."

Rudich is editor of the Journal of Cryptology and was selected by the Mathematical Association of America as Pólya Lecturer for the 2004–2005 and 2005–2006 academic years. An accomplished magician, he also serves as director of Andrew's Leap, a highly selective summer program for Pittsburgh-area high school students interested in math and science.

Razborov is an editor of the Theoretical Computer Science journal and was awarded the Nevanlinna Prize of the International Mathematical Union in 1990 for his contributions to complexity theory.

Source: Carnegie Mellon University

Researcher study effectiveness of traditional and blended learning environments
In today's online era, the concept of a classroom extends beyond a walled room with desks and chairs and into the realm of cyber space. Computer screens are replacing the blackboard and keypads are replacing chalk. To provide learners with the best experience, many educators are opting for a blended approach: a traditional classroom with face-to-face interaction supplemented by online resources. One University of Missouri researcher has found that while this approach is currently not necessarily more effective, there is hope for developing an effective hybrid approach to learning.
Best way to treat malaria: Avoid using same drug for everyone, scientists say
(PhysOrg.com) -- A team of scientists employing a sophisticated computer model pioneered at Princeton University and Resources for the Future has found that many governments worldwide are recommending the wrong kind of malaria treatment.
Amateur Astronomers See Perseids Hit the Moon
One, the old-fashioned way: Find a dark place with starry skies and count the meteors streaking overhead. Two, the new way: Find a dark place with starry skies and then completely ignore the meteors. Instead, watch the Moon. That's where the explosions are.
Stanford's 'autonomous' helicopters teach themselves to fly
Stanford computer scientists have developed an artificial intelligence system that enables robotic helicopters to teach themselves to fly difficult stunts by watching other helicopters perform the same maneuvers. The result is an autonomous helicopter than can perform a complete airshow of complex tricks on its own.
Using everyday language to explain scientific concepts could help students learn, study finds
(PhysOrg.com) -- To talk about photosynthesis, you need to know a little Latin, a bit of French, some Greek, a word coined by a pair of French chemists in the 19th century, and a word of ancient origin that has been adopted and adapted by scientists around the world.
Students who use 'clickers' score better on physics tests
Hand-held electronic devices called clickers are helping college students learn physics, according to a series of research studies.
Semantics gives the web meaning -- for machines
(PhysOrg.com) -- Where would we be without the web? It is such an immense and rich source of information; we feel that every answer is out there. All it takes is a bit of searching...
Web of possibilities: Researcher finds new avenues for social research online
Why do certain songs become hits while others flop? How can individuals be encouraged to consider the public good rather than act selfishly? Why are casual relationships sometimes as important as connections to friends and family?

CMU professor honored for computational complexity breakthrough

Related stories:

News discussion: