ounting problems are studied in a variety of areas. For example, enumerative combinatorics, statistics, statistical physics, and artificial intelligence.;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 (;To tackle ;For HARDCORE(lambda), we extend Sly's results (Sly, 2010) and almost resolve the computational complexity of approximating the partition function of the hardcore model on graphs of maximum degree Delta. We prove for every Delta ≥ 3 except Delta ∈ {4, 5}, unless NP=RP, there does not exist a fully polynomial randomized approximation scheme (FPRAS) for HARDCORE(lambda) when lambda > lambda c( TD ), where lambdac( TD ) is the threshold for the uniqueness of Gibbs measures on infinite Delta-regular trees.;For ;We explore applications of an FPRAS for ;For
展开▼
