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.
* 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...