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.

Versions

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.

BibTeX entry

@misc{Vadhan95,
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 ]