Showing math.COShow all
2 papers · 1 filter
math.CO2025
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 -XORSAT problem. Specifically, we derive an expli…
math.CO2025
Asymptotic size of the Karp-Sipser Core in Configuration Model
Arnab Chatterjee, Joon Hyung Lee, Haodong Zhu
We study the asymptotic size of the Karp-Sipser core in the configuration model with arbitrary degree distributions. The Karp-Sipser core is the induced subgraph obtained by iterat…