论文标题
改进的随机CNF公式的采样解决方案的边界
Improved Bounds for Sampling Solutions of Random CNF Formulas
论文作者
论文摘要
令$φ$为$ n $变量和$ m $ chauses上的随机$ k $ -cnf公式，其中每个子句都是独立和均匀选择的$ k $文字的脱节。我们的目标是采样$φ$的大约均匀解决方案（或等效地，近似$φ$的分区函数）。 令$α= m/n $为密度。以前的最佳算法在时间上运行$ n^{\ mathsf {poly}（k，α）} $，对于任何$α\ lyseSim2^{k/300} $ [Galanis，Goldberg，Guo，Guo和Yang，Siam J. Comput.'21]。我们的结果通过为任何$α\ Lessim2^{k/3} $提供几乎线性的时间采样器，从而显着提高了这两个界限。 密度$α$在随机公式中捕获\ emph {平均度}。在具有界限\ emph {最高度}的最坏情况模型中，当前最佳有效采样器的限制为$ 2^{k/5} $ [He，Wang和Yin和Yin，focs'22和Soda'23]，这是首次由于其平均案例，由于我们的$ 2^^{k/3} $第一次取代。我们的结果是确定直觉的第一个进展是，平均案例模型（随机$ K $ -CNF公式具有限制平均水平）比最差的案例模型（标准$ K $ -CNF公式具有最大值的最大程度）在采样溶液中。
Let $Φ$ be a random $k$-CNF formula on $n$ variables and $m$ clauses, where each clause is a disjunction of $k$ literals chosen independently and uniformly. Our goal is to sample an approximately uniform solution of $Φ$ (or equivalently, approximate the partition function of $Φ$). Let $α=m/n$ be the density. The previous best algorithm runs in time $n^{\mathsf{poly}(k,α)}$ for any $α\lesssim2^{k/300}$ [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. Our result significantly improves both bounds by providing an almost-linear time sampler for any $α\lesssim2^{k/3}$. The density $α$ captures the \emph{average degree} in the random formula. In the worst-case model with bounded \emph{maximum degree}, current best efficient sampler works up to degree bound $2^{k/5}$ [He, Wang, and Yin, FOCS'22 and SODA'23], which is, for the first time, superseded by its average-case counterpart due to our $2^{k/3}$ bound. Our result is the first progress towards establishing the intuition that the solvability of the average-case model (random $k$-CNF formula with bounded average degree) is better than the worst-case model (standard $k$-CNF formula with bounded maximal degree) in terms of sampling solutions.
