{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:07Z","timestamp":1759637707630,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,6,14]],"date-time":"2015-06-14T00:00:00Z","timestamp":1434240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1319811,CCF-1016799"],"award-info":[{"award-number":["CCF-1319811,CCF-1016799"]}]},{"name":"ERC","award":["617951"],"award-info":[{"award-number":["617951"]}]},{"name":"NWO","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,6,14]]},"DOI":"10.1145\/2746539.2746607","type":"proceedings-article","created":{"date-parts":[[2015,6,3]],"date-time":"2015-06-03T15:35:56Z","timestamp":1433345756000},"page":"193-200","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Lov\u00e1sz Theta function for Independent Sets in Sparse Graphs"],"prefix":"10.1145","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"given":"Guru","family":"Guruganesh","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]}],"member":"320","published-online":{"date-parts":[[2015,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579451"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581168"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1910"},{"key":"e_1_3_2_1_6_1","volume-title":"The Probabilistic Method","author":"Alon N.","year":"1992","unstructured":"N. Alon and J. Spencer . The Probabilistic Method . Wiley Interscience , New York , 1992 . N. Alon and J. Spencer. The Probabilistic Method. Wiley Interscience, New York, 1992."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a003"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722130"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488665"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611465"},{"key":"e_1_3_2_1_12_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Hos P.","year":"1935","unstructured":"P. Erd\\ Hos and G. Szekeres . A combinatorial problem in geometry . Compositio Mathematica , 2 : 463 -- 470 , 1935 . P. Erd\\Hos and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463--470, 1935.","journal-title":"Compositio Mathematica"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_3_2_1_14_1","volume-title":"Separation between estimation and approximation. Electronic Colloquium on Computational Complexity (ECCC), 21:110","author":"Feige U.","year":"2014","unstructured":"U. Feige and S. Jozeph . Separation between estimation and approximation. Electronic Colloquium on Computational Complexity (ECCC), 21:110 , 2014 . U. Feige and S. Jozeph. Separation between estimation and approximation. Electronic Colloquium on Computational Complexity (ECCC), 21:110, 2014."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.09.003"},{"key":"e_1_3_2_1_16_1","volume-title":"Approximation algorithms and semidefinite programming","author":"Matousek B.","year":"2012","unstructured":"B. G\\\"artner and J. Matousek . Approximation algorithms and semidefinite programming . Springer , Heidelberg , 2012 . B. G\\\"artner and J. Matousek. Approximation algorithms and semidefinite programming. Springer, Heidelberg, 2012."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1097"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_3_2_1_19_1","volume-title":"Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl., 4:no. 1, 16 pp","author":"Halld\u00f3rsson M. M.","year":"2000","unstructured":"M. M. Halld\u00f3rsson . Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl., 4:no. 1, 16 pp ., 2000 . M. M. Halld\u00f3rsson. Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl., 4:no. 1, 16 pp., 2000."},{"issue":"4","key":"e_1_3_2_1_20_1","first-page":"475","article-title":"Improved approximations of independent sets in bounded-degree graphs via subgraph removal","volume":"1","author":"Halld\u00f3rsson M. M.","year":"1994","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan . Improved approximations of independent sets in bounded-degree graphs via subgraph removal . Nord. J. Comput. , 1 ( 4 ): 475 -- 492 , 1994 . M. M. Halld\u00f3rsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nord. J. Comput., 1(4):475--492, 1994.","journal-title":"Nord. J. Comput."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700381097"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875499"},{"key":"e_1_3_2_1_23_1","volume-title":"preprint","author":"Johansson A.","year":"1996","unstructured":"A. Johansson . Asymptotic choice number for triangle-free graphs. preprint , 1996 . A. Johansson. Asymptotic choice number for triangle-free graphs. preprint, 1996."},{"key":"e_1_3_2_1_24_1","volume-title":"August","author":"Johansson A.","year":"1996","unstructured":"A. Johansson . The choice number of sparse graphs. preprint , August 1996 . A. Johansson. The choice number of sparse graphs. preprint, August 1996."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_21"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001528"},{"key":"e_1_3_2_1_28_1","volume-title":"Networks and semidefinite programming (lecture notes","author":"Laurent M.","year":"2014","unstructured":"M. Laurent . Networks and semidefinite programming (lecture notes 2014 ). http:\/\/homepages.cwi.nl\/ monique\/lnmb14\/lnmb14.pdf. M. Laurent. Networks and semidefinite programming (lecture notes 2014). http:\/\/homepages.cwi.nl\/ monique\/lnmb14\/lnmb14.pdf."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90273-X"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070305"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004898"}],"event":{"name":"STOC '15: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Portland Oregon USA","acronym":"STOC '15"},"container-title":["Proceedings of the forty-seventh annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2746539.2746607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:00Z","timestamp":1750227420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,14]]},"references-count":34,"alternative-id":["10.1145\/2746539.2746607","10.1145\/2746539"],"URL":"https:\/\/doi.org\/10.1145\/2746539.2746607","relation":{},"subject":[],"published":{"date-parts":[[2015,6,14]]},"assertion":[{"value":"2015-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}