The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-call...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2015
|
| _version_ | 1797075279224504320 |
|---|---|
| author | Galanis, A Goldberg, L |
| author_facet | Galanis, A Goldberg, L |
| author_sort | Galanis, A |
| collection | OXFORD |
| description | One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite Δ-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on k-uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric k-ary Boolean function f there exists a degree bound Δ0 so that for all Δ ≥ Δ0 the following problem is NP-hard: given a k-uniform hypergraph with maximum degree at most Δ, approximate the partition function of the hypergraph 2-spin model associated with f. It is NP-hard to approximate this partition function even within an exponential factor. By contrast, if f is a trivial symmetric Boolean function (e.g., any function f that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time. |
| first_indexed | 2024-03-06T23:48:12Z |
| format | Conference item |
| id | oxford-uuid:71ad0c77-d422-4522-b87e-fa370c0f005a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:48:12Z |
| publishDate | 2015 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:71ad0c77-d422-4522-b87e-fa370c0f005a2022-03-26T19:45:14ZThe complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:71ad0c77-d422-4522-b87e-fa370c0f005aEnglishSymplectic Elements at OxfordSociety for Industrial and Applied Mathematics2015Galanis, AGoldberg, LOne of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite Δ-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on k-uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric k-ary Boolean function f there exists a degree bound Δ0 so that for all Δ ≥ Δ0 the following problem is NP-hard: given a k-uniform hypergraph with maximum degree at most Δ, approximate the partition function of the hypergraph 2-spin model associated with f. It is NP-hard to approximate this partition function even within an exponential factor. By contrast, if f is a trivial symmetric Boolean function (e.g., any function f that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time. |
| spellingShingle | Galanis, A Goldberg, L The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs |
| title | The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs |
| title_full | The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs |
| title_fullStr | The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs |
| title_full_unstemmed | The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs |
| title_short | The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs |
| title_sort | complexity of approximately counting in 2 spin systems on k uniform bounded degree hypergraphs |
| work_keys_str_mv | AT galanisa thecomplexityofapproximatelycountingin2spinsystemsonkuniformboundeddegreehypergraphs AT goldbergl thecomplexityofapproximatelycountingin2spinsystemsonkuniformboundeddegreehypergraphs AT galanisa complexityofapproximatelycountingin2spinsystemsonkuniformboundeddegreehypergraphs AT goldbergl complexityofapproximatelycountingin2spinsystemsonkuniformboundeddegreehypergraphs |