Approximately counting independent sets in dense bipartite graphs via subspace enumeration

Charlie Carlson, Ewan Davies, Alexandra Kolla +1

We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for…