The Complexity of Counting

Salil P. Vadhan

This is my undergraduate thesis, done in 1995 under the supervision of Leslie Valiant at Harvard University.  It has a self-contained exposition of Valiant's theory of #P-completness, along with new #P-completeness results for counting independent sets, matchings, vertex covers, and extremal variants of these in bipartite graphs of bounded degree.


BibTeX entry

author = "Salil P. Vadhan",
title = "The Complexity of Counting",
howpublished = "Undergraduate thesis, Harvard University",
year = "1995",
note = "Available from \verb||"

[ back to Salil Vadhan's research interests ]