License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.63
URN: urn:nbn:de:0030-drops-164047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16404/
Galanis, Andreas ;
Štefankovič, Daniel ;
Vigoda, Eric
Approximating Observables Is as Hard as Counting
Abstract
We study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph. A recent work of Galanis et al (2021) established NP-hardness of approximating the average size of an independent set utilizing hardness of the corresponding optimization problem and the related phase transition behavior. We instead consider settings where the underlying optimization problem is easily solvable. Our main contribution is to classify the complexity of approximating a wide class of observables via a generic reduction from approximate counting to the problem of estimating local observables. The key idea is to use the observables to interpolate the counting problem.
Using this new approach, we are able to study observables on bipartite graphs where the underlying optimization problem is easy but the counting problem is believed to be hard. The most-well studied class of graphs that was excluded from previous hardness results were bipartite graphs. We establish hardness for estimating the average size of the independent set in bipartite graphs of maximum degree 6; more generally, we show tight hardness results for general vertex-edge observables for antiferromagnetic 2-spin systems on bipartite graphs. Our techniques go beyond 2-spin systems, and for the ferromagnetic Potts model we establish hardness of approximating the number of monochromatic edges in the same region as known hardness of approximate counting results.
BibTeX - Entry
@InProceedings{galanis_et_al:LIPIcs.ICALP.2022.63,
author = {Galanis, Andreas and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric},
title = {{Approximating Observables Is as Hard as Counting}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {63:1--63:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16404},
URN = {urn:nbn:de:0030-drops-164047},
doi = {10.4230/LIPIcs.ICALP.2022.63},
annote = {Keywords: Approximate Counting, Averages, Phase Transitions, Random Structures}
}
|
Keywords: |
|
Approximate Counting, Averages, Phase Transitions, Random Structures |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
