[2106.12710] Certifying solution geometry in random CSPs: counts, clusters and b...
source link: https://arxiv.org/abs/2106.12710
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 24 Jun 2021]
Certifying solution geometry in random CSPs: counts, clusters and balance
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.
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2106.12710 [cs.DS] |
| (or arXiv:2106.12710v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2106.12710 |
Recommend
-
14
The data In the examples shown in this article, I will be using a data set taken from the Kaggle website. It is designed for a machine learning classification task and contains information about medical appoint...
-
8
Browser Engines 2015: Commit Rates and Active Developer Counts Nov 4, 2015 I used to work as a developer in the “core” group at Opera that developed the Presto web engine. During this period, I often wondered just how ma...
-
7
Executing Word Counts with Bash Apr 12, 2017 I'm in the process of starting a new writing project and I wanted to make the process of getting metrics easier so I rolled together this bash script:
-
5
Revised Download Counts and Package StatisticsMaarten BalliauwSeptember...
-
12
Why every millisecond counts when code testing mobile apps January 21, 2021 Alex Drag
-
9
Experience counts - public Qualtrics gets off to a strong start as customers re-shape for a post-COVID world
-
9
GETTR Is the Trump Team’s Buggy, Leaky Twitter CloneImage: GETTROn Thursday, Politico revealed that Donald Trump's former sp...
-
31
America's FAA Shifts Gears Slightly on Certifying Future 'Flying Taxi' Pilots Become a fan of Slash...
-
6
Microsoft announces stretched clusters and more for Azure VMware Solution...
-
7
SpatialRandom Geometry Generation with PostGISA user on the
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK