Belief Propagation Guided Decimation on Random k-XORSAT

Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang +3

We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random $k$-XORSAT problem. Specifically, we derive an expli…