4

[2207.11892] Improved Bounds for Sampling Solutions of Random CNF Formulas

 2 years ago
source link: https://arxiv.org/abs/2207.11892
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.
neoserver,ios ssh client

[Submitted on 25 Jul 2022]

Improved Bounds for Sampling Solutions of Random CNF Formulas

Download PDF

Let \Phi 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, for most \Phi, to (approximately) uniformly sample from its solution space.
Let \alpha=m/n be the density. The previous best algorithm runs in time n^{\mathsf{poly}(k,\alpha)} for any \alpha\lesssim2^{k/300} [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. In contrast, our algorithm runs in near-linear time for any \alpha\lesssim2^{k/3}.

Comments: SODA'23 submission version
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Probability (math.PR)
Cite as: arXiv:2207.11892 [cs.DS]
  (or arXiv:2207.11892v1 [cs.DS] for this version)
  https://doi.org/10.48550/arXiv.2207.11892

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK