[12] S. Sengupta, S. Rayanchu, and S. Banerjee, "Network coding-aware routing in wireless networks," *IEEE/ACM Trans. Netw.*, vol. 18, no. 4, pp. 1158–1170, Aug. 2010.

[13] M. Kim, M. Medard, U.-M. O'Reilly, and D. Traskov, "An evolutionary ´
approach to inter-session network coding," in *INFOCOM*, 2009, pp.

450–458.

[14] J. Barcelo, B. Bellalta, C. Cano, A. Sfairopoulou, M. Oliver, and K. Verma, "Towards a collision-free WLAN: Dynamic parameter adjustment in CSMA/E2CA," EURASIP Journal on Wireless Communications and Networking, 2011.

[15] M. Fang, D. Malone, K.R. Duffy, and D.J. Leith, "Decentralised learning MACs for collision-free access in WLANs," *Wirel. Netw.*, vol. To appear, 2012.

[16] M. Davis and H. Putnam, "A computing procedure for quantification theory," *J. ACM*, vol. 7, pp. 201–215, July 1960.

[17] M. Davis, G. Logemann, and D. Loveland, "A machine program for theorem-proving," *Commun. ACM*, vol. 5, pp. 394–397, July 1962.

[18] Y. Hamadi and S. Jabbour, "ManySAT: a parallel SAT solver," *JSAT*,
vol. 6, no. 4, pp. 245–262, 2009.

[19] Ming Ouyang, "How good are branching rules in DPLL?," Discrete Appl. Math., vol. 89, pp. 281–286, December 1998.

[20] J. Pearl, "Reverend Bayes on inference engines: a distributed hierarchical approach," in *Procedings of American Association for Artificial* Intelligence National Conference on AI, 1982, pp. 133–136.

[21] M. Mezard and R. Zecchina, "Random ´ k-satisfiability problem: From an analytic solution to an efficient algorithm," *Phys. Rev. E*, vol. 66, no.

5, pp. 056126, Nov 2002.

[22] C.H. Papadimitriou, "On selecting a satisfying truth assignment," in IEEE Symposium on Foundations of Computer Science (FOCS ). 1991, pp. 162–169, IEEE Computer Society, New York.

[23] U. Schoning, "A probabilistic algorithm for k-SAT and constraint satisfaction problems," in IEEE Symposium on Foundations of Computer Science (FOCS ). 1999, pp. 410–414, IEEE Computer Society, New York.

[24] D. Achlioptas, A. Naor, and Y. Peres, "Rigorous location of phase transitions in hard optimization problems," *Nature*, vol. 435, no. 9, pp.

759–764, 2005.

[25] D. Achlioptas and Y. Peres, "The threshold for random k-SAT is 2k log 2-O(k)," *J. Amer. Math. Soc.*, vol. 17, no. 4, pp. 947–973, 2004.

[26] A.C. Kaporis, L.M. Kirousis, and E.G. Lalas, "The probabilistic analysis of a greedy satisfiability algorithm," *Rand. Struct. Algorithms*, vol. 28, no. 4, pp. 444–480, 2006.

[27] A. M. Frieze and S. Suen, "Analysis of two simple heuristics on a random instance of k-SAT," *J. Algorithms*, vol. 20, no. 2, pp. 312?355, 1996.

[28] S. Mertens, M. Mezard, and R. Zecchina, "Threshold values of random k-SAT from the cavity method," *Rand. Struct. Algorithms*, vol. 28, no.

3, pp. 340–37, 2005.

[29] F Krzakala, A. Montarani, Ricci-Tersenghi F., G. Semerijan, and L. Zdeborova, "Gibbs states and the set of solutions of random constraint satisfaction problems," *Proc. Natl. Acad. Sci. USA*, vol. 104, no. 25, pp.

10318–10323, 2007.

[30] E. Aurell, U. Gordon, and S. Kirkpatrick, "Comparing beliefs, surveys and random walks," in *Advances in Neural Information Processing* Systems (NIPS). 2004, vol. 17, pp. 49–56, MIT Press, Boston.

[31] M. Mezard, G. Parisi, and R. Zecchina, "Analytic and algorithmic solution of random satisfiability problems," *Science*, vol. 297, pp. 812–
815, 2002.

[32] M. Mezard, T. Mora, and R. Zecchina, "Clustering of solutions in the random satisfiability problem," *Phys. Rev. Lett.*, vol. 94, pp. 197–205, 2005.

[33] M. Alava, J. Ardeliu, E. Aurell, P. Kaski, S. Krishnamurthy, and P. Orponen, "Circumspect descent prevails in solving random constraint satisfaction problems," *Proc. Natl. Acad. Sci. USA*, vol. 105, no. 4, pp.

15253–15257, 2008.

[34] M. Alekhnovich and E. Ben-Sasson, "Linear upper bounds for random walk on small density 3-CNFs," *SIAM J. Comput.*, vol. 36, no. 5, pp.

1248–1263, 2006.

[35] WIGLE.NET, ," http://www.wigle.net/, 2010.

[36] *Part 11: Wireless LAN Medium Access Control (MAC) and Physical* Layer (PHY) Specifications. Further Higher Data Rate Extension in the 2.4GHz Band, IEEE, New York, 2003.

[37] A. Goldsmith, *Wireless Communications*, Cambridge University Press, 2005.

[38] M. F. Barnsley, S. G. Demko, J. H. Elton, and J. S. Geronimo, "Invariant measures for Markov processes arising from iterated function systems with place-dependent probabilities," *Ann. Inst. H. Poincare Probab.* ´
Statist., vol. 24, no. 3, pp. 367–394, 1988.