Random local access for sampling k-SAT solutions

Dingding Dong, Nitya Mani

We present a sublinear time algorithm that gives random local access to the uniform distribution over satisfying assignments to an arbitrary k-SAT formula $\hat{I}¦$, at exponential clau…