{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T17:06:03Z","timestamp":1648832763353},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2002,11,21]],"date-time":"2002-11-21T00:00:00Z","timestamp":1037836800000},"content-version":"unspecified","delay-in-days":20,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2002,11]]},"abstract":"<jats:p>We show that recognizing the <jats:italic>K<\/jats:italic><jats:sup>3<\/jats:sup>-freeness and <jats:italic>K<\/jats:italic><jats:sup>4<\/jats:sup>-freeness of graphs is hard, respectively, for \ntwo-player nondeterministic communication protocols using exponentially many partitions \nand for nondeterministic syntactic read-<jats:italic>r<\/jats:italic> times branching programs.<\/jats:p><jats:p>The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and \nSipser, which says that for every balanced red\u2014blue colouring of the edges of the complete \n<jats:italic>n<\/jats:italic>-vertex graph there is a set of \u03b5<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> triangles, none of which is monochromatic, such that \nno triangle can be formed by picking edges from different triangles. We extend this lemma \nto <jats:italic>exponentially many<\/jats:italic> colourings and to <jats:italic>partial<\/jats:italic> colourings.<\/jats:p>","DOI":"10.1017\/s0963548302005333","type":"journal-article","created":{"date-parts":[[2002,11,26]],"date-time":"2002-11-26T09:34:58Z","timestamp":1038303298000},"page":"549-569","source":"Crossref","is-referenced-by-count":3,"title":["Triangle-Freeness is Hard to Detect"],"prefix":"10.1017","volume":"11","author":[{"given":"S.","family":"JUKNA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"SCHNITGER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2002,11,21]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548302005333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T20:24:14Z","timestamp":1557174254000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548302005333\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":0,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["S0963548302005333"],"URL":"https:\/\/doi.org\/10.1017\/s0963548302005333","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}