On the geometry of $k$-SAT solutions: what more can PPZ and Sch\"oning's algorithms do?
<|reference_start|>On the geometry of $k$-SAT solutions: what more can PPZ and Sch\"oning's algorithms do?: Given a $k$-CNF formula and an integer $s$, we study algorithms that obtain $s$ solutions to the formula that are maximally dispersed. For $s=2$, the problem of computing the diameter of a $k$-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for $k=2$. Assuming SETH, the current best upper bound [Angelsmark and Thapper '04] goes to $4^n$ as $k \rightarrow \infty$. As our first result, we give exact algorithms for using the Fast Fourier Transform and clique-finding that run in $O^*(2^{(s-1)n})$ and $O^*(s^2 |\Omega_{F}|^{\omega \lceil s/3 \rceil})$ respectively, where $|\Omega_{F}|$ is the size of the solution space of the formula $F$ and $\omega$ is the matrix multiplication exponent.   As our main result, we re-analyze the popular PPZ (Paturi, Pudlak, Zane '97) and Sch\"{o}ning's ('02) algorithms (which find one solution in time $O^*(2^{\varepsilon_{k}n})$ for $\varepsilon_{k} \approx 1-\Theta(1/k)$), and show that in the same time, they can be used to approximate the diameter as well as the dispersion ($s>2$) problems. While we need to modify Sch\"{o}ning's original algorithm, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe that this property may be of independent interest.   Finally, we present algorithms to output approximately diverse, approximately optimal solutions to NP-complete optimization problems running in time $\text{poly}(s)O^*(2^{\varepsilon n})$ with $\varepsilon<1$ for several problems such as Minimum Hitting Set and Feedback Vertex Set. For these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions $s$. Our methods find bi-approximations with polynomial dependence on $s$.<|reference_end|>
@article{austrin2024on,
    title={On the geometry of $k$-SAT solutions: what more can PPZ and Sch\"oning's
  algorithms do?},
    author={Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh
  Srinivasan},
    journal={arXiv preprint arXiv:2408.03465},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.03465},
    primaryClass={cs.CC cs.DS}
}