Harvard computer scientist Leslie Valiant wins Turing Award | Hacker News Reader

Harvard computer scientist Leslie Valiant wins Turing Award

networkworld.com

82 pointsalphadoggs12 comments

Prof. Leslie Valiant has done awesome work in complexity theory. Among other things, he:

* introduced the notion of #P [1]. Replacing the "Is there any ..." question in an NP problem with "How many ... " makes a problem #P e.g. "Is there any subset in this list of integers that adds up to zero" is an NP problem, "How many subsets add up to zero" is a #P problem. This class also includes the problem of doing exact inference in a general graphical model.

* introduced the "Probably Approximately Correct" notion in machine learning for analyzing various learning techniques. [2]

* with Vijay Vazirani, stated & proved the Valiant-Vazirani theorem [3] that, in essence, showed that the intractability of NP problems is not related to the wide variation in possible solutions for the problem. E.g. the Satisfiability problem could have anywhere from zero to exponentially many solutions, but this variance is not the reason it is hard.

[1] http://qwiki.stanford.edu/index.php/Complexity_Zoo:Symbols#s...

[2] http://web.mit.edu/6.435/www/Valiant84.pdf

[3] http://www.cs.princeton.edu/courses/archive/fall05/cos528/ha...

* The algorithm that shares his namesake, an extension of the CYK algorithm (a parsing algorithm for context-free grammars), is the fastest known.[1]

[1] Leslie G. Valiant. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:2 (1975), 308–314.

Note that the Turing Award != Turing Test, which was my initial (excited) thought.

That a Harvard professor was able to convince an observer he was, in fact, human?

Or, you know, the author of such a system (being an AI expert and all)

http://www.amazon.com/Most-Human-Talking-Computers-Teaches/d...

The author of this book was a guest on The Daily Show recently and mentioned that there is an award given to the human who is most convincing to the judges that he or she is a human. (I'm not sure which Turing Test event he was talking about specifically.)

I didn't know or even stop to consider this before, but it is interesting to think about what makes our written speech seem human.

This is admittedly getting off-topic.

He was my undergrad advisor, and I have to say, he never convinced me.

Anyone want to wager on the next three Turing Award winners?

My nominations:

Peter Shor

Maurice Herlihy

Richard Stallman

Mario Szegedy

Bill Dally

Richard Stallman

hmmm, i think Turing Awards are more biased towards theoretical contributions to CS (even for systems people). Although Stallman has made great contributions to the field of computing, he isn't an academic CS researcher, so he might not be in the running :/

I thought about that too, so I had checked what ACM said:

"It is given to an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the computer field"

I think his work with GNU has been one of the most important technical contributions to the community we've seen.

On a non-technical note, his push for free software has also been incredibly influential for the community. While I disagree with a lot of ideology and in particular the ideology behind the GPL personally, I think the world is generally better for it.

I would not be surprised if Maurice Herlihy managed to get a Turing Award in the next few years.

I would be surprised if Stallman got a Turing Award however. I can't think of anything beyond his philosophy that makes him stand out in any technically innovative way.

From http://en.wikipedia.org/wiki/Richard_Stallman

"Stallman has also developed a number of pieces of widely used software, including the original Emacs, the GNU Compiler Collection, the GNU Debugger, and many tools in the GNU Coreutils."

Reply on news.ycombinator.com