Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Counterexamples to a Weitz-Style Reduction for Multispin Systems
Kuikui Liu, Nitya Mani, Francisco Pernice
In a seminal paper, Weitz showed that for two-state spin systems, such as the Ising and hardcore models from statistical physics, correlation decay on trees implies correlation dec…
cs.DS2024
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 , at exponential claus…