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.