{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:35Z","timestamp":1759637915342},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:00:00Z","timestamp":1154563200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Autom Reasoning"],"published-print":{"date-parts":[[2006,10,5]]},"DOI":"10.1007\/s10817-005-9012-z","type":"journal-article","created":{"date-parts":[[2006,8,2]],"date-time":"2006-08-02T22:36:51Z","timestamp":1154558211000},"page":"181-200","source":"Crossref","is-referenced-by-count":13,"title":["Regular Random k-SAT: Properties of Balanced Formulas"],"prefix":"10.1007","volume":"35","author":[{"given":"Yacine","family":"Boufkhad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Dubois","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannet","family":"Interian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bart","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,8,3]]},"reference":[{"key":"9012_CR1","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"Achlioptas, D. (2001): Lower bounds for random 3-SAT via differential equations, Theor. Comp. Sci. 265, pp. 159\u2013185.","journal-title":"Theor. Comp. Sci."},{"key":"9012_CR2","doi-asserted-by":"crossref","unstructured":"Achlioptas, D. and Moore, C. (2002): The asymptotic order of the random k-SAT threshold, in 43th Annual Symposium on Foundations of Computer Science, Vancouver, pp. 779\u2013788.","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"9012_CR3","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1090\/S0894-0347-04-00464-3","volume":"17","author":"D. Achlioptas","year":"2004","unstructured":"Achlioptas, D. and Peres, Y. (2004): The threshold for random k-SAT is 2 k ln2 \u2013O(k), J. Amer. Math. Soc. 17, 947\u2013973.","journal-title":"J. Amer. Math. Soc."},{"key":"9012_CR4","unstructured":"Achlioptas, D., Gomes, C. P., Kautz, H. A., and Selman, B. (2000): Generating satisfiable problems instances, in Proceedings of 17th National Conference on Artificial Intelligence, pp. 256\u2013261."},{"key":"9012_CR5","doi-asserted-by":"crossref","unstructured":"Bayardo, R. J. and Schrag, R. (1996): Using CSP look-back techniques to solve exceptionally hard SAT instances, in Proceedings of the Second Int. Conf. on Principles and Practice of Constraint Programming, pp. 46\u201360.","DOI":"10.1007\/3-540-61551-2_65"},{"key":"9012_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs Second Edition","author":"B. Bollobas","year":"2001","unstructured":"Bollobas, B. (2001): Random Graphs Second Edition, Cambridge University Press, United Kingdom."},{"key":"9012_CR7","unstructured":"Chvatal, V. and Reed, B. (1992): Mick gets some (the odds are on his side). Proceedings of 33rd FOCS, pp. 620\u2013627."},{"key":"9012_CR8","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chvatal","year":"1988","unstructured":"Chvatal, V. and Szemeredi, E. (1988): Many hard examples for resolution, J. Assoc. Comput. Mach. 35 759\u2013768.","journal-title":"J. Assoc. Comput. Mach."},{"key":"9012_CR9","unstructured":"Cooper, C., Frieze, A. and Sorkin, G. B. (2002): A note on random 2-SAT with prescribed literal degrees. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"9012_CR10","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0304-3975(01)00161-X","volume":"265","author":"O. Dubois","year":"2001","unstructured":"Dubois, O. (2001): Upper bounds on the satisfiability threshold, Theor. Comput. Sci. Vol. 265, 187\u2013197.","journal-title":"Theor. Comput. Sci. Vol."},{"issue":"2","key":"9012_CR11","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1997.0867","volume":"24","author":"O. Dubois","year":"1997","unstructured":"Dubois, O. and Boufkhad, Y. (1997): A general upper bound for the satisfiability threshold of random r-SAT formulae, J. Algorithms 24(2), 395\u2013420.","journal-title":"J. Algorithms"},{"key":"9012_CR12","unstructured":"Dubois, O. and Dequen, G. (2001): A backbone search heuristic for efficient solving of hard 3-SAT formulae, in Proceedings of 17th International Joint Conference on Artificial Intelligence, Seattle, pp. 248\u2013253."},{"key":"9012_CR13","unstructured":"Dubois, O., Boufkhad, Y. and Mandler, J. (2000): Typical random 3-SAT formulae and the satisfiability threshold, in SODA, pp. 126\u2013127. Full version in Electronic Colloquium on Computational Complexity (ECCC 2003)."},{"key":"9012_CR14","unstructured":"Fernandez de la Vega, W. (1992): On random 2-SAT. Manuscript."},{"key":"9012_CR15","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E. (1999): Sharp thresholds for graph properties and the k-sat problem, J. Amer. Math. Soc. 12, 1017\u20131054.","journal-title":"J. Amer. Math. Soc."},{"issue":"3","key":"9012_CR16","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","author":"A. Goerdt","year":"1996","unstructured":"Goerdt, A. (1996): A threshold for unsatisfiability, J. Comput. Syst. Sci. 53(3), 469\u2013486.","journal-title":"J. Comput. Syst. Sci."},{"key":"9012_CR17","unstructured":"Hajiaghayi, M. and Sorkin, G. (2004) The satisfiability threshold of random 3-SAT is at least 3.52. www.math.mit.edu\/hajiagha\/3satRCl.ps ."},{"key":"9012_CR18","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000)","unstructured":"Janson, S., Luczak, T. and Rucinski, A. (2002): Random Graphs, Wiley, New York."},{"key":"9012_CR19","doi-asserted-by":"crossref","unstructured":"Kaporis, A. C., Kirousis, L. M. and Lalas, E. G. (2002): The probabilistic analysis of a greedy satisfiability algorithm, in 10th Annual European Symposium on Algorithms.","DOI":"10.1007\/3-540-45749-6_51"},{"key":"9012_CR20","doi-asserted-by":"crossref","unstructured":"Kaporis, A. C., Kirousis, L. M. and Lalas, E. (2003): Selecting complementary pairs of literals. Electron. Notes Discrete Mathem. 16.","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"9012_CR21","doi-asserted-by":"crossref","unstructured":"Kautz, H., Ruan, Y., Achlioptas, D., Gomes, C. P., Selman, B. and Stickel, M. (2001): Balance and filtering in structured satisfiable problems, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence.","DOI":"10.1016\/S1571-0653(04)00310-5"},{"issue":"3","key":"9012_CR22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","volume":"12","author":"L. M. Kirousis","year":"1998","unstructured":"Kirousis, L. M., Kranakis, E., Krizanc, D. and Stamatiou, Y. C. (1998): Approximating the unsatisfiability threshold of random formulas, Random Struct. Algorithms 12(3), 253\u2013269.","journal-title":"Random Struct. Algorithms"},{"key":"9012_CR23","unstructured":"Le Berre, D. and Simon, L. (2004): SAT competitions. http:\/\/www.lri.fr\/simon\/contest\/results\/"},{"key":"9012_CR24","unstructured":"Li, C.-M.: SATZ. http:\/\/www.laria.u-picardie.fr\/cli\/EnglishPage.html ."},{"key":"9012_CR25","unstructured":"Mitchell, D., Selman, B. and Levesque, H. (1992): Hard and easy distributions of SAT problems, in Proceedings of the 10th National Conf. on Artificial Intelligence, pp. 459\u2013465."},{"issue":"4","key":"9012_CR26","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N. C. Wormald","year":"1995","unstructured":"Wormald, N. C. (1995): Differential equations for random processes and random graphs, Ann. Appl. Probab. 5(4), 1217\u20131235.","journal-title":"Ann. Appl. Probab."}],"container-title":["Journal of Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-005-9012-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10817-005-9012-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-005-9012-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T01:21:46Z","timestamp":1559265706000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10817-005-9012-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8,3]]},"references-count":26,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2006,10,5]]}},"alternative-id":["9012"],"URL":"https:\/\/doi.org\/10.1007\/s10817-005-9012-z","relation":{},"ISSN":["0168-7433","1573-0670"],"issn-type":[{"value":"0168-7433","type":"print"},{"value":"1573-0670","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,8,3]]}}}