{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T10:04:25Z","timestamp":1774260265025,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2014,2,28]],"date-time":"2014-02-28T00:00:00Z","timestamp":1393545600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s11432-013-5052-x","type":"journal-article","created":{"date-parts":[[2014,2,28]],"date-time":"2014-02-28T10:00:34Z","timestamp":1393581634000},"page":"1-9","source":"Crossref","is-referenced-by-count":5,"title":["An upper (lower) bound for Max (Min) CSP"],"prefix":"10.1007","volume":"57","author":[{"given":"Ping","family":"Huang","sequence":"first","affiliation":[]},{"given":"MingHao","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,2,28]]},"reference":[{"key":"5052_CR1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C E Shannon","year":"1948","unstructured":"Shannon C E. A mathematical theory of communication. Bell Syst Tech J, 1948, 27:379\u2013423","journal-title":"Bell Syst Tech J"},{"key":"5052_CR2","doi-asserted-by":"crossref","unstructured":"Creignou N, Khanna S, Sudan M. Complexity Classifications of Boolean Constraint Satisfaction Problems. In: Monographs on Discrete Mathematics and Applications, Vol. 7. SIAM, 2001","DOI":"10.1137\/1.9780898718546"},{"key":"5052_CR3","volume-title":"Oxford University Press","author":"P Hell","year":"2004","unstructured":"Hell P, Nesetril J. Graphs and Homomorphisms. Oxford University Press, 2004"},{"key":"5052_CR4","unstructured":"Cheeseman P, Kanefsky B, Taylor W M. Where the really hard problems are. In: Proceedings of IJCAI-91, Sydney, 1991. 331\u2013337"},{"key":"5052_CR5","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"A C Kaporis","year":"2006","unstructured":"Kaporis A C, Kirousis L M, Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm. Random Struct Algor, 2006, 28:444\u2013480","journal-title":"Random Struct Algor"},{"key":"5052_CR6","unstructured":"D\u00edaz Cort J, Lefteris K, Mitsche D, et al. A new upper bound for 3-SAT. In: Proceedings of FSTTCS\u2019 08, Bangalore, 2008. 163\u2013174"},{"key":"5052_CR7","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B M Smith","year":"1996","unstructured":"Smith B M, Dyer M E. Locating the phase transition in binary constraint satisfaction problems. Artif Intell, 1996, 81:155\u2013181","journal-title":"Artif Intell"},{"key":"5052_CR8","first-page":"107","volume-title":"Stamatiou: Random Constraint Satisfaction: A More Accurate Picture","author":"D Achlioptas","year":"1997","unstructured":"Achlioptas D, Kirousis L M, Kranakis E, et al. Stamatiou: Random Constraint Satisfaction: A More Accurate Picture. Berlin\/Heidelberg: Springer, 1997. 107\u2013120"},{"key":"5052_CR9","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K Xu","year":"2007","unstructured":"Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171:514\u2013534","journal-title":"Artif Intell"},{"key":"5052_CR10","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K Xu","year":"2000","unstructured":"Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res, 2000, 12:93\u2013103","journal-title":"J Artif Intell Res"},{"key":"5052_CR11","first-page":"1790","volume-title":"Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco","author":"P Huang","year":"2011","unstructured":"Huang P, Yin M H, Xu K. Exact phase transitions and approximate algorithm of #CSP. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, 2011. 1790\u20131791"},{"key":"5052_CR12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.1006","volume":"18","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s B, Borgs C, Chayes J T, et al. The scaling window of the 2-SAT transition. Random Struct Algor, 2001, 18:201\u2013256","journal-title":"Random Struct Algor"},{"key":"5052_CR13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J Gramm","year":"2003","unstructured":"Gramm J, Hirsch E A, Niedermeier R, et al. Worst-case upper bounds for MAX-2-SAT with an application to MAXCUT. Discrete Appl Math, 2003, 130:139\u2013155","journal-title":"Discrete Appl Math"},{"key":"5052_CR14","series-title":"Lect Notes in Comput Sci","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-46541-3_5","volume-title":"Proceedings of 17th International Symposium on Theoretical Aspects of Computer Science","author":"E A Hirsch","year":"2000","unstructured":"Hirsch E A. A new algorithm for MAX-2-SAT. In: Proceedings of 17th International Symposium on Theoretical Aspects of Computer Science. Lect Notes in Comput Sci, vol. 1770. Springer-Verlag, 2000. 65\u201373"},{"key":"5052_CR15","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1002\/rsa.20015","volume":"24","author":"D Coppersmith","year":"2004","unstructured":"Coppersmith D, Gamarnik D, Hajiaghayi M T, et al. Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct Algor, 2004, 24:502\u2013545","journal-title":"Random Struct Algor"},{"key":"5052_CR16","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.ipl.2010.11.002","volume":"111","author":"X L Xu","year":"2011","unstructured":"Xu X L, Gao Z S, Xu K. A tighter upper bound for random MAX 2-SAT. Inf Process Lett, 2011, 111:115\u2013119","journal-title":"Inf Process Lett"},{"key":"5052_CR17","first-page":"605","volume-title":"Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Bellaterra","author":"C M Li","year":"2011","unstructured":"Li C M, Zhu Z, Many\u00e0 F, et al. Minimum satisfiability and its applications. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Bellaterra, 2011. 605\u2013610"},{"key":"5052_CR18","first-page":"256","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence","author":"D Achlioptas","year":"2000","unstructured":"Achlioptas D, Gomes C, Kautz H, et al. Generating satisfiable problem instances. In: Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence, 2000. 256\u2013261"},{"key":"5052_CR19","first-page":"611","volume":"1","author":"T Liu","year":"2011","unstructured":"Liu T, Lin X, Wang C, et al. Large hinge width on sparse random hypergraphs. In: Proceedings of the 22th International Joint Conference on Artificial Intelligence, vol. 1, 2011. 611\u2013616","journal-title":"Proceedings of the 22th International Joint Conference on Artificial Intelligence"},{"key":"5052_CR20","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.tcs.2006.01.001","volume":"355","author":"K Xu","year":"2006","unstructured":"Xu K, Li W. Many hard examples in exact phase transitions. Theor Comput Sci, 2006, 355:291\u2013302","journal-title":"Theor Comput Sci"},{"key":"5052_CR21","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1142\/S012905411000774X","volume":"21","author":"J Zhou","year":"2010","unstructured":"Zhou J, Huang P, Yin M, et al. Phase transitions of EXPSPACE-complete problems. Int J Found Comput Sci, 2010, 21:1073\u20131088","journal-title":"Int J Found Comput Sci"},{"key":"5052_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1142\/S0129054112500025","volume":"23","author":"J Zhou","year":"2012","unstructured":"Zhou J, Yin M, Li X, et al. Phase transitions of EXPSPACE-complete problems: a further step. Int J Found Comput Sci, 2012, 23:173\u2013184","journal-title":"Int J Found Comput Sci"},{"key":"5052_CR23","first-page":"364","volume-title":"Phase Transitions in Knowledge Compilation: An Experimental Study","author":"J Gao","year":"2011","unstructured":"Gao J, Yin M, Xu K. Phase Transitions in Knowledge Compilation: An Experimental Study. Berlin\/Heidelberg: Springer, 2011. 364\u2013366"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-013-5052-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-013-5052-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-013-5052-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T22:11:09Z","timestamp":1565215869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-013-5052-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2,28]]},"references-count":23,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["5052"],"URL":"https:\/\/doi.org\/10.1007\/s11432-013-5052-x","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2,28]]}}}