论文标题
从算法到连通性和返回：在随机K-Sat中找到一个巨大的组件
From algorithms to connectivity and back: finding a giant component in random k-SAT
论文作者
论文摘要
我们采用算法方法来研究相对稀疏的随机和有限度的$ k $ -cnfs的解决方案空间几何形状。在这样做的过程中，我们确定具有$ n $变量的随机$ k $ -cnf $φ$和条款密度$α= m/n = m/n \ lissSim 2^{k/6} $具有巨大的解决方案的巨大组件，它们在图中相互连接，如果它们相邻$ o__k（$ o o_k（$ o o_k（ $ k $ -cnfs的密度相似。我们还能够在类似的制度中推断出随机和有限程度$ k $ -cnfs的松散结果。 尽管我们的主要动机是了解解决方案空间的几何形状，但我们的方法具有算法含义。为此，我们构建了一个理想化的块动力学，该动力学从随机的$ k $ -cnf $φ$中采样密度$α= m/n \ lyseSim 2^{k/52} $。我们表明，这款马尔可夫链可以在多项式时间内实现高概率，并且通过利用光谱独立性，我们还观察到它会相对较快，从而使多项式时间算法与较高的概率样本均匀的随机解决方案与随机$ K $ -CNF进行了均匀的随机解决方案。我们的工作表明，在存在巨大组件时，自然固定的途径是开发以随机$ k $ -cnfs进行抽样解决方案的清晰算法。
We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree $k$-CNFs for large $k$. In the course of doing so, we establish that with high probability, a random $k$-CNF $Φ$ with $n$ variables and clause density $α= m/n \lesssim 2^{k/6}$ has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance $O_k(\log n)$ and that a similar result holds for bounded degree $k$-CNFs at similar densities. We are also able to deduce looseness results for random and bounded degree $k$-CNFs in a similar regime. Although our main motivation was understanding the geometry of the solution space, our methods have algorithmic implications. Towards that end, we construct an idealized block dynamics that samples solutions from a random $k$-CNF $Φ$ with density $α= m/n \lesssim 2^{k/52}$. We show this Markov chain can with high probability be implemented in polynomial time and by leveraging spectral independence, we also observe that it mixes relatively fast, giving a polynomial time algorithm to with high probability sample a uniformly random solution to a random $k$-CNF. Our work suggests that the natural route to pinning down when a giant component exists is to develop sharper algorithms for sampling solutions in random $k$-CNFs.
