In this dissertation, we investigate several counting problems, which are subjects of active research. The specific problems considered are: counting independent sets in bipartite graphs (#BIS), computing the partition function of the hard-core model (Hardcore($\lambda$)), counting Eulerian tours (#ET), counting weighted matchings in bipartite graphs (#BipMatch) and related problems, and counting $q$-colorings (#$q$-Coloring). We study these problems from the viewpoint of exact counting, i.e., whether one can efficiently compute the answers exactly, as well as the viewpoint of approximability, i.e., whether one can efficiently compute the answers approximately.
To tackle #BIS, we create a new graph polynomial: the $R_2$ polynomial. The most interesting property of this polynomial is that it encodes the number of independent sets in bipartite graphs. We investigate properties of the $R_2$ polynomial, the computational complexity of exact evaluation of the polynomial at various points, and the problem of approximate evaluation of the polynomial.
For Hardcore($\lambda$), we extend Sly's results and almost resolve the computational complexity of approximating the partition function of the hard-core model on graphs of maximum degree $\Delta$. We prove for every $\Delta \geq 3$ except $\Delta \in \{4,5\}$, unless NP$=$RP, there does not exist an FPRAS for Hardcore($\lambda$) when $\lambda>\lambda_c(\Tree_{\Delta})$, where $\lambda_c(\Tree_{\Delta})$ is the threshold for the uniqueness of Gibbs measures on infinite $\Delta$-regular trees.
For #ET and its variation #A-trail, we prove #P-completeness results for the exact computation of #ET in $4$-regular graphs and #A-trail in $4$-regular maps. We also establish a reduction from the approximate computation of #ET in Eulerian graphs to the approximate computation of #A-trail in $4$-regular maps.
We explore applications of an FPRAS for #BipMatch and two related matching problems which generalize #BipMatch. We analyze properties of match-gates and develop an FPRAS for a variation of the ICE model using match-gates.
For #$q$-Coloring, we establish the strong spatial mixing of $q$-colorings on $(b+1)$-regular Bethe lattices, for $q \geq 1+\lceil 1.764b \rceil$. We also establish the strong spatial mixing of $q$-colorings on binary trees, for $q=4$.