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.CCC.2022.11
URN: urn:nbn:de:0030-drops-165735
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16573/
Hsieh, Jun-Ting ;
Mohanty, Sidhanth ;
Xu, Jeff
Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance
Abstract
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the density, for which a precise landscape of predictions has been made via statistical physics-based heuristics. In parallel, there has been a recent flurry of work on refuting random constraint satisfaction problems, via nailing refutation thresholds for spectral and semidefinite programming-based algorithms, and also on counting solutions to CSPs. Inspired by this, the starting point for our work is the following question: What does the solution space for a random CSP look like to an efficient algorithm?
In pursuit of this inquiry, we focus on the following problems about random Boolean CSPs at the densities where they are unsatisfiable but no refutation algorithm is known.
1) Counts. For every Boolean CSP we give algorithms that with high probability certify a subexponential upper bound on the number of solutions. We also give algorithms to certify a bound on the number of large cuts in a Gaussian-weighted graph, and the number of large independent sets in a random d-regular graph.
2) Clusters. For Boolean 3CSPs we give algorithms that with high probability certify an upper bound on the number of clusters of solutions.
3) Balance. We also give algorithms that with high probability certify that there are no "unbalanced" solutions, i.e., solutions where the fraction of +1s deviates significantly from 50%. Finally, we also provide hardness evidence suggesting that our algorithms for counting are optimal.
BibTeX - Entry
@InProceedings{hsieh_et_al:LIPIcs.CCC.2022.11,
author = {Hsieh, Jun-Ting and Mohanty, Sidhanth and Xu, Jeff},
title = {{Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {11:1--11:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-241-9},
ISSN = {1868-8969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16573},
URN = {urn:nbn:de:0030-drops-165735},
doi = {10.4230/LIPIcs.CCC.2022.11},
annote = {Keywords: constraint satisfaction problems, certified counting, random graphs}
}
|
Keywords: |
|
constraint satisfaction problems, certified counting, random graphs |
|
Collection: |
|
37th Computational Complexity Conference (CCC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
11.07.2022 |
