{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,21]],"date-time":"2025-04-21T21:01:49Z","timestamp":1745269309050},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2018,4,2]],"date-time":"2018-04-02T00:00:00Z","timestamp":1522627200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,9]]},"abstract":"<jats:p>NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been proved to be easy. We show the intractability of <jats:italic>random<\/jats:italic> instances of a graph colouring problem: this graph problem is hard on average unless all NP problems under all samplable (<jats:italic>i.e.<\/jats:italic> generatable in polynomial time) distributions are easy. Worst case reductions use special gadgets and typically map instances into a negligible fraction of possible outputs. Ours must output nearly random graphs and avoid any super-polynomial distortion of probabilities. This poses significant technical difficulties.<\/jats:p>","DOI":"10.1017\/s0963548318000123","type":"journal-article","created":{"date-parts":[[2018,4,2]],"date-time":"2018-04-02T03:55:23Z","timestamp":1522641323000},"page":"808-828","source":"Crossref","is-referenced-by-count":2,"title":["An Average Case NP-complete Graph Colouring Problem"],"prefix":"10.1017","volume":"27","author":[{"given":"LEONID A.","family":"LEVIN","sequence":"first","affiliation":[]},{"given":"RAMARATHNAM","family":"VENKATESAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,4,2]]},"reference":[{"key":"S0963548318000123_ref34","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225153"},{"key":"S0963548318000123_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"S0963548318000123_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.70"},{"key":"S0963548318000123_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"S0963548318000123_ref10","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s","year":"2004"},{"key":"S0963548318000123_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73027"},{"key":"S0963548318000123_ref29","volume-title":"Computation: Finite and Infinite Machines","author":"Minsky","year":"1967"},{"key":"S0963548318000123_ref5","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2015-0010"},{"key":"S0963548318000123_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"S0963548318000123_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"S0963548318000123_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"S0963548318000123_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90007-R"},{"key":"S0963548318000123_ref28","doi-asserted-by":"crossref","unstructured":"Micciancio D. and Regev O. (2004) Worst case to average case reductions using Gaussian measures. In FOCS '04: Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 372\u2013381.","DOI":"10.1109\/FOCS.2004.72"},{"key":"S0963548318000123_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89604"},{"key":"S0963548318000123_ref17","volume-title":"Proc. Inst. of Electrical Communications","author":"Ikeno","year":"1958"},{"key":"S0963548318000123_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90032-4"},{"key":"S0963548318000123_ref12","first-page":"111","volume-title":"SFCS '87: 28th Annual Symposium on Foundations of Computer Science","author":"Gurevich","year":"1987"},{"key":"S0963548318000123_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548318000123_ref25","volume-title":"The Development of the Number Field Sieve","author":"Lenstra","year":"1991"},{"key":"S0963548318000123_ref20","first-page":"1","volume-title":"Algorithms and Complexity","author":"Karp","year":"1976"},{"key":"S0963548318000123_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008619"},{"key":"S0963548318000123_ref30","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.5"},{"key":"S0963548318000123_ref31","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62231"},{"key":"S0963548318000123_ref16","first-page":"601","volume-title":"Combinatorial Theory and its Applications, II","author":"Hajnal","year":"1970"},{"key":"S0963548318000123_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237838"},{"key":"S0963548318000123_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0216034"},{"key":"S0963548318000123_ref21","volume-title":"Combinatorial Optimization: Annotated Bibliographies","author":"Karp","year":"1985"},{"key":"S0963548318000123_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"S0963548318000123_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2008.11.006"},{"key":"S0963548318000123_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792232070"},{"key":"S0963548318000123_ref33","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"},{"key":"S0963548318000123_ref27","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023634616182"},{"key":"S0963548318000123_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129774"},{"key":"S0963548318000123_ref14","first-page":"802","article-title":"Matrix decomposition is complete for the average case","volume":"2","author":"Gurevich","year":"1990","journal-title":"IEEE FOCS"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T16:50:44Z","timestamp":1555174244000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000123\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,2]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["S0963548318000123"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000123","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,2]]}}}