Fast sampling of satisfying assignments from random $k$-SAT with applications to connectivity

Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
The asymptotic $k$-SAT threshold
Random generation of combinatorial structures from a uniform distribution
Asymptotic lower bounds for Ramsey functions
High order random walks: beyond spectral gap
The number of solutions for random regular NAE-SAT
Belief propagation on the random $k$-SAT model
Proof of the satisfiability conjecture for large $k$
Approximation algorithms for the normalizing constant of Gibbs distributions
Pairs of SAT-assignments in random Boolean formulæ
Analyzing Walksat on Random Formulas
The Number of Satisfying Assignments of Random Regulark-SAT Formulas
Adaptive simulated annealing: A near-optimal connection between sampling and counting
A constructive proof of the general lovász local lemma
Analysis of Two Simple Heuristics on a Random Instance ofk-sat
The Decimation Process in Random $k$-SAT
Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
Counting Solutions to Random CNF Formulas
Improved analysis of higher order random walks and applications
Rapid mixing of hypergraph independent sets
Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models
Gibbs states and the set of solutions of random constraint satisfaction problems
A Better Algorithm for Random k-SAT
New Constructive Aspects of the Lovász Local Lemma
Probability and Computing
On the solution‐space geometry of random constraint satisfaction problems
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
Sampling constraint satisfaction solutions in the local lemma regime
The number of satisfying assignments of random 2‐SAT formulas
Improved Bounds for Sampling Solutions of Random CNF Formulas
Deterministic counting Lov\'{a}sz local lemma beyond linear programming
Fast sampling via spectral independence beyond bounded-degree graphs
On mixing of Markov chains: coupling, spectral independence, and entropy factorization

This page was built for publication: Fast sampling of satisfying assignments from random $k$-SAT with applications to connectivity

Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity