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.

- Undergraduate thesis, Harvard University, 1995. [ postscript ] [ compressed postscript ]
- The main results of this thesis were later published in the paper The Complexity of Counting in Sparse, Regular, and Planar Graphs.

author = "Salil P. Vadhan",

title = "The Complexity of Counting",

howpublished = "Undergraduate thesis, Harvard University",

year = "1995",

note = "Available from \verb|http://people.seas.harvard.edu/~salil/|"

}

[ back to Salil Vadhan's research interests ]