Fast sampling of satisfying assignments from random k-SAT with applications to connectivity
We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random k-SAT model when the density of the formula scales exponentially with k. The best previously known sampling algorithm for the random k-SAT model applies when the density α = m/n of the formula is less...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2024
|