Coja-Oghlan, Amin (2011) On belief propagation guided decimation for random k-SAT. In: Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 23 - 25 Jan 2011. Published in: SODA '11 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms pp. 957-966.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-constructive arguments show that Φ is satisfiable for clause/variable ratios m/n ≤ rk ~ 2k ln 2 with high probability (Achlioptas, Moore: SICOMP 2006; Achlioptas, Peres: J. AMS 2004). Yet no efficient algorithm is know to find a satisfying assignment for densities as low as m/n ~ rk · ln(k)/k with a non-vanishing probability. In fact, the density m/n ~ rk · ln(k)/k seems to form a barrier for a broad class of local search algorithms (Achlioptas, Coja-Oghlan: FOCS 2008). On the basis of deep but non-rigorous statistical mechanics considerations, a message passing algorithm called belief propagation guided decimation for solving random k-SAT has been forward (Mézard, Parisi, Zecchina: Science 2002; Braunstein, Mézard, Zecchina: RSA 2005). Experiments suggest that the algorithm might succeed for densities very close to rk for k = 3, 4, 5 (Kroc, Sabharwal, Selman: SAC 2009). Furnishing the first rigorous analysis of belief propagation guided decimation on random k-SAT, the present paper shows that the algorithm fails to find a satisfying assignment already for m/n ≥ ρ · rk/k, for a constant ρ > 0 independent of k.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	SODA '11 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher:	SIAM
Official Date:	2011
Dates:	Date Event 2011 Published
Page Range:	pp. 957-966
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
Type of Event:	Other
Location of Event:	San Francisco, CA, USA
Date(s) of Event:	23 - 25 Jan 2011

Request changes or add full text files to a record

Repository staff actions (login required)

View Item