From algorithms to connectivity and back: finding a giant component in random k-SAT

Zongchen Chen, Nitya Mani, Ankur Moitra

We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree $k$-CNFs for large $k$. In the course of doing so, we establi…