[Computational Complexity] Valiant wins EATCS award
- 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.
- Defined #P and showed Perm was NP-complete and also that most NPC problems have #P analogs.
- 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.
- Defined PAC learning.
- Defined Superconcentrators- a kind of expander graph.
- Started Algebraic analogs of Boolean Complexity.
- Had some stuff on parallelism.
- Started the recent Matchgate algorithm paradigm.
- Put up with me being his TA for Combinatorics.
Posted By GASARCH to Computational Complexity at 2/15/2008 10:33:00 AM