Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Achlioptas, L. M. Kirousis, E. Kranakis, and D. Krizanc. Rigorous results for random (2 +p)-SAT. In Proceedings of RALCOM 97 (Santorini, Greece), pages 1-13, 1997. Submitted to Theoret. Comput. Sci.
	2	P. Beame and T. Pitassi. Propositional proof complexity: past, present, and future. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (65):66-89, 1998.
	3	B. Bollobfis, C. Borgs, J. Chayes, J. H. Kim, and D. B. Wilson. The scaling window of the 2-SAT transition. Manuscript, 1999.
	4	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.322-330, January 25-27, 1993, Austin, Texas, United States
	5	Ming-Te Chao , John Franco, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM Journal on Computing, v.15 n.4, p.1106-1118, Nov. 1986 [doi>10.1137/0215080]
	6	V. Chv~tal and B. Reed. Mick gets some (the odds are on his side). In 33th Annual Symposium on Foundations o/Computer Science (Pittsburgh, PA, 199~), pages 620-627. iEEE Comput. Soc. Press, Los Alamitos, CA, 1992.
	7	Vašek Chvátal , Endre Szemerédi, Many hard examples for resolution, Journal of the ACM (JACM), v.35 n.4, p.759-768, Oct. 1988 [doi>10.1145/48014.48016]
	8	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	9	S. A. Cook and D. G. Mitchell. Finding hard instances of the satisfiability problem: a survey. In Satisfiability problem: theory and applications (Piscataway, N J, 1996), pages 1-17. Amer. Math. Soc., Providence, RI, 1997.
	10	Martin Davis , George Logemann , Donald Loveland, A machine program for theorem-proving, Communications of the ACM, v.5 n.7, p.394-397, July 1962 [doi>10.1145/368273.368557]
	11	Martin Davis , Hilary Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM (JACM), v.7 n.3, p.201-215, July 1960 [doi>10.1145/321033.321034]
	12	O. Dubois , Y. Boufkhad, A general upper bound for the satisfiability threshold of random r-SAT formulae, Journal of Algorithms, v.24 n.2, p.395-420, Aug. 1997 [doi>10.1006/jagm.1997.0867]
	13	Olivier Dubois , Yacine Boufkhad , Jacques Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 09-11, 2000, San Francisco, California, United States
	14	A. El Maftouhi and W. Fernandez de la Vega. On random 3-SAT. Combin. Probab. Comput., 4(3):189-195, 1995.
	15	W. Fernandez de la Vega. On random 2-SAT. 1992. Manuscript.
	16	J. Franco. Probabilistic analysis of the pure literal heuristic for the satisfiability problem. Ann. Oper. Res., 1:273-289, 1984.
	17	J. Franco and M. Paul1. Probabilistic analysis of the Davis-Putnam procedure for solving the satisftability problem. Discrete Appl. Math., 5(1):77-87, 1983.
	18	E. Friedgut. Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12:1017-1054, 1999.
	19	Alan Frieze , Stephen Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms, v.20 n.2, p.312-355, March 1996 [doi>10.1006/jagm.1996.0016]
	20	Andreas Goerdt, A threshold for unsatisfiability, Journal of Computer and System Sciences, v.53 n.3, p.469-486, Dec. 1996 [doi>10.1006/jcss.1996.0081]
	21	A. Goldberg. On the complexity of the satisfiability problem. In jth Workshop on Automated Deduction (Austin, TX, 1979), pages 1-6, 1979.
	22	A. Haken. The intractability of resolution. Theoret. Comput. Sci., 39(2-3):297-308, 1985.
	23	S. Janson, Y. C. Stamatiou, and M. Vamwakari. Bounding the unsatisfiability threshold of random 3-SAT. 1999. Submitted.
	24	Anil Kamath , Rajeev Motwani , Paul Spirakis , Krishna Palem, Tail bounds for occupancy and the satisfiability threshold conjecture, Random Structures & Algorithms, v.7 n.1, p.59-80, Aug. 1995 [doi>10.1002/rsa.3240070105]
	25	R. Karp and M. Sipser. Maximum matchings in sparse random graphs. In 2~nd Annual Symposium on Foundations of Computer Science, pages 364-375. IEEE Cornput. Soc. Press, Los Alamitos, CA, 1981.
	26	Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Yannis C. Stamatiou, Approximating the unsatisfiability threshold of random formulas, Random Structures & Algorithms, v.12 n.3, p.253-269, May 1998 [doi>10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U]
	27	T. G. Kurtz. Solutions of ordinary differential equations as limits of pure jump Markov processes. J. Appl. Probability, 7:49-58, 1970.
	28	T. G. Kurtz. Approximation of population processes. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1981.
	29	A. W. Marshall and I. Olkin. Inequalities: theory of majorization and its applications. Academic Press Inc. {Harcourt Brace Jovanovich Publishers}, New York, 1979.
	30	R. Monasson and R. Zecchina. Entropy of the K- satisfiability problem. Phys. Rev. Left., 76(21):3881- 3885, 1996.
	31	R. Monasson and R. Zecchina. Statistical mechanics of the random K-satisfiability model. Phys. Rev. E (3), 56(2):1357-1370, 1997.
	32	R. Monasson and R. Zecchina. Tricritical points in random combinatorics: the (2 + p)-SAT case. J. Phys. A, 1998. submitted.
	33	R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Phase transition and search cost in the (2 + p)-SAT problem. In Jth Workshop on Physics and Computation, (Boston, MA, 1996).
	34	R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic phase transitions. Nature, 400:133-137, 1999.
	35	Nedialko Stoyanov Nedialkov , K. R. Jackson, Computing rigorous bounds on the solution of an initial value problem for an ordinary differential equation, 1999
	36	Darren Redfern, The Maple handbook (Maple V release 3), Springer-Verlag New York, Inc., New York, NY, 1994
	37	Bart Selman , David G. Mitchell , Hector J. Levesque, Generating hard satisfiability problems, Artificial Intelligence, v.81 n.1-2, p.17-29, March 1996 [doi>10.1016/0004-3702(95)00045-3]
	38	N. C. Wormald. Differential equations for random processes and random graphs. Ann. Appl. Probab., 5(4):1217-1235, 1995.