Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Valiant wins EATCS award

Expand Messages
  • GASARCH
    Valiant won the EATCS award. This was already reported on Luca Aceto s blog To goto Valiants website go here To goto the EATCS annoucement of why they are
    Message 1 of 1 , Feb 15, 2008
      Valiant won the EATCS award. This was already reported on Luca Aceto's blog To goto Valiants website go here To goto the EATCS annoucement of why they are giving it to Valiant go here

      So what has Valiant done? Here is an incomplete high level list which may be exaggerated.
      1. Defined #P and showed Perm was NP-complete and also that most NPC problems have #P analogs.
      2. Was co-author on Valiant-Vazarani paper (duh). Main result: if given a formula that you KNOW has either 0 or 1 SAT assignments, telling which one is hard (unless NP=R). Was also a first step towards Toda's theorem.
      3. Defined PAC learning.
      4. Defined Superconcentrators- a kind of expander graph.
      5. Started Algebraic analogs of Boolean Complexity.
      6. Had some stuff on parallelism.
      7. Started the recent Matchgate algorithm paradigm.
      8. Put up with me being his TA for Combinatorics.
      I'm surprised he hasn't won the Turing Award yet, but I'm sure he will.

      --
      Posted By GASARCH to Computational Complexity at 2/15/2008 10:33:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.