Sampling k-SAT Solutions Sampling almost uniform k-SAT solution under LLL-like condition? Mathematics and Computation [Wigderson 2020]: COAFU7A0米 Ar Myeason "the solution space (and hence the natural Markov chain)is not connected" Random walk in solution space (Markov chain Monte Carlo,MCMC): e ere here! Rapid Mixing Slow (Torpid)Mixing Not Mixing• Sampling almost uniform k-SAT solution under LLL-like condition? • Random walk in solution space (Markov chain Monte Carlo, MCMC): Sampling k-SAT Solutions “the solution space (and hence the natural Markov chain) is not connected” Mathematics and Computation [Wigderson 2020]: Rapid Mixing Slow (Torpid) Mixing Not Mixing We ere here!