{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:39Z","timestamp":1781077779093,"version":"3.54.1"},"reference-count":21,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181879","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T15:35:00Z","timestamp":1056641700000},"page":"23-32","source":"Crossref","is-referenced-by-count":19,"title":["Hardness results for coloring 3-colorable 3-uniform hypergraphs"],"prefix":"10.1109","author":[{"given":"S.","family":"Khot","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"19","first-page":"3","article-title":"Coverings and colorings of hypergraphs","author":"lova?sz","year":"1973","journal-title":"Proc of 4th Southeastern Conf on Combinatorics Graph Theory and Computing"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004334"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1173"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959936"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509962"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365710"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253464"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258536"},{"key":"12","article-title":"Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 ?","author":"holmerin","year":"0","journal-title":"Proc of the 34th Annual ACM Symposium on Theory of Computing 2002"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276869"},{"key":"3","article-title":"Free bits, pcps and non-approximability","author":"bellare","year":"1995","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"10","first-page":"627","article-title":"Clique is hard to approximate within n1-?","author":"ha?stad","year":"1996","journal-title":"In Proceedings of IEEE Annual Symposium on Foundations of Computer Science"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181880"},{"key":"5","article-title":"k - 1 - ? hardness for vertex cover in k-uniform hypergraphs","author":"dinur","year":"0"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"9","first-page":"319","article-title":"Coloring k-colorable graphs using smaller palettes","author":"halperin","year":"2001","journal-title":"Proc 13th Annu Symp Discrete Algorithms"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892074"}],"event":{"name":"43rd Annual IEEE Symposium on Foundations of Computer Science","location":"Vancouver, BC, Canada","acronym":"SFCS-02"},"container-title":["The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8411\/26517\/01181879.pdf?arnumber=1181879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,14]],"date-time":"2017-03-14T00:20:35Z","timestamp":1489450835000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181879\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":21,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181879","relation":{},"subject":[]}}