Wednesday, March 09, 2011

Les Valiant wins the Turing Award

In a definite case of when not if, Leslie Valiant will receive the 2010 ACM Turing Award, the highest honor in all of computer science. Valiant has done incredible work in learning theory (he invented PAC learning), parallel and distributed computing and more recently holographic algorithms. Valiant's brilliant work in counting complexity, including the #P-completeness of the Permanent and his work with Vijay Vazirani that shows that solving NP problems with a single solution is as hard as arbitrary NP problems, have played a critical role in much of my own research.

Valiant will give his Turing Award lecture at FCRC in San Jose on the evening of Sunday June 5th, which will be a special treat for those of us going to STOC or the other FCRC meetings.
Posted by at

14 comments:

  1. Anonymous9:37 AM, March 09, 2011

    1) For a long time Les Valiant was one of the best theorists who had NOT won a Turing award. This distinction is now lost.
    Oh Well.

    2) Les Valiant is impressive in that he does not take his eye off the ball. He pursued hard questions, makes progress,
    and then moves on to other problems rather than making an entire career out of
    one area.

    ReplyDelete
  2. Anonymous10:42 AM, March 09, 2011

    Well said for (2), Papadimitriou might be at a similar situation. Consequently, their contributions are much bigger than somebody doing one thing for their whole life (like computational geometry --- no bad feelings for geometers though).

    ReplyDelete
  3. ._.10:46 AM, March 09, 2011

    Eventually he's awarded! I supposed that he must have been nominated five years ago. :)

    ReplyDelete
  4. dick lipton11:46 AM, March 09, 2011

    Wonderful choice. Agree with all you said.

    ReplyDelete
  5. Anonymous12:39 AM, March 10, 2011

    Well said for (2), ... Consequently, their contributions are much bigger than somebody doing one thing for their whole life (like computational geometry --- no bad feelings for geometers though).

    This is an interesting point. But I actually admire more those who have dedicated their whole career to a single big and ambitious problem. It seems that this is the way to attain maximal depth. Though, probably indeed this makes less influence on the short term (and sometimes even on the long term) - which is in fact not always a bad sign.

    ReplyDelete
  6. Anonymous2:54 AM, March 10, 2011

    Good news!

    ReplyDelete
  7. Anonymous5:06 AM, March 10, 2011

    I supposed that he must have been nominated five years ago.

    Nearly so.

    For a long time Les Valiant was one of the best theorists who had NOT won a Turing award.

    It is my understanding that this was because he hadn't been nominated before. This was his first time up.

    An outstanding choice by ACM.

    ReplyDelete
  8. NickH7:45 AM, March 10, 2011

    It is my understanding that Valiant is also responsible for introducing Chernoff bounds into the TCS community. For example, the Raghavan-Thompson paper cites the Angluin-Valiant '77 paper as their source for Chernoff bounds.

    ReplyDelete
  9. Anonymous10:54 AM, March 10, 2011

    It is my understanding that this was because he hadn't been nominated before. This was his first time up.

    Actually, he had been nominated before. There are many reasons why nominations don't work out, and the process is difficult to predict or control.

    ReplyDelete
  10. Anonymous2:48 AM, March 11, 2011

    Who are the most likely candidates for the next theorist to win a Turing Award? Someone mentioned Papadimitriou. Who are the other suspects in contention?

    ReplyDelete
  11. Anonymous3:47 AM, March 11, 2011

    Actually, he had been nominated before.

    I understand a nomination enters a queue and may take a while to work through the system. So if someone nominates person X in 2008 and 2010 it might feel like two kicks at the can, but this isn't really the case.

    Then again I might be wrong. It is not like the committee openly discusses this, though general procedure is not a secret either. Your sources are as good as mine.

    ReplyDelete
  12. GASARCH9:23 AM, March 11, 2011

    Other candidates: Wigderson or perhaps
    Nisan and Wigderson jointly.
    If its for one thing then perhaps all of the authors on the two PCP papers.
    If its for lifetime achievement then perhaps a subset of them, though that could get... awkward. Looking at the winners it is not clear if its for
    one thing or a lifetime thing.

    Pure speculation about Valiant: He is somewhat shy and I cannot picture him asking people to nominate him or write him letters and such. That might have delayed it.

    ReplyDelete
  13. Anonymous2:50 PM, March 11, 2011

    Les Valiant rightly deserves the Turing award and imo, it was long overdue. Having won a Nevanlinna prize, a Guggenheim fellowship,
    and a Knuth prize, let alone a NAS membership, it was probably the only award left to be bestowed on him.
    Better late than never, i guess.

    ReplyDelete
  14. Geoff Knauth3:50 AM, March 14, 2011

    Valiant mentioned by Ian Islick in Using 100% of your brain. Addresses tweet I saw questioning why Valiant was cited by NYTimes for AI.

    ReplyDelete

Subscribe to: Post Comments (Atom)