Abstract
We study the problem of approximately counting independent sets in hypergraphs with maximum degree Delta whose hyperedges have arity at least k>=3. In the graphical case, where the arity of every edge is 2, it is known that for Delta>=6 the problem is hard and for Delta<=5 there is an FPTAS. This approximation algorithm uses correlation decay techniques that rely on the fact that strong spatial mixing occurs.
Surprisingly, in the hypergraph case we give a correlation decay based algorithm even though strong spatial mixing fails. Our main idea is introducing amortization in the correlation decay proof. In particular, in the correlation decay proof we track not just the decay but also combinatorial properties of the intermediate instances. This enables us to give an FPTAS even when strong spatial mixing fails, for example, when Delta=6 and k>=3 and also for all Delta and all sufficiently large k>=1.66*Delta. We further demonstrate that in the hypergraph independent set model, approximating the partition function is NP-hard even within the uniqueness regime.
Joint work with Ivona Bezakova, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic.