{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:42:32Z","timestamp":1781077352527,"version":"3.54.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,12,31]],"date-time":"2015-12-31T00:00:00Z","timestamp":1451520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["434923"],"award-info":[{"award-number":["434923"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2010418"],"award-info":[{"award-number":["2010418"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001658","name":"Minerva Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001658","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["45208"],"award-info":[{"award-number":["45208"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n                    We study the well-known\n                    <jats:italic toggle=\"yes\">Label Cover<\/jats:italic>\n                    problem under the additional requirement that problem instances have large girth. We show that if the girth is some\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    , the problem is roughly 2\n                    <jats:sup>\n                      log\n                      <jats:sup>1-\u03f5<\/jats:sup>\n                      <jats:italic toggle=\"yes\">n)\/k<\/jats:italic>\n                    <\/jats:sup>\n                    hard to approximate for all constant \u03f5 &gt; 0. A similar theorem was claimed by Elkin and Peleg [2000] as part of an attempt to prove hardness for the basic\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -spanner problem, but their proof was later found to have a fundamental error. Thus, we give both\n                    <jats:italic toggle=\"yes\">the first<\/jats:italic>\n                    nontrivial lower bound for the problem of Label Cover with large girth as well as the first full proof of strong hardness for the basic\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming\n                    <jats:italic toggle=\"yes\">NP<\/jats:italic>\n                    \u2286\n                    <jats:italic toggle=\"yes\">BPTIME<\/jats:italic>\n                    (2\n                    <jats:sup>\n                      <jats:italic toggle=\"yes\">polylog(n)<\/jats:italic>\n                    <\/jats:sup>\n                    , we show (roughly) that for every\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    \u2a7e 3 and every constant \u03f5 &gt; 0, it is hard to approximate the basic\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -spanner problem within a factor better than 2\n                    <jats:sup>\n                      log\n                      <jats:sup>1-\u03f5<\/jats:sup>\n                      <jats:italic toggle=\"yes\">n)\/k<\/jats:italic>\n                    <\/jats:sup>\n                    . This improves over the previous best lower bound of only \u03a9(log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    )\/\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    from Kortsarz [2001]. Our main technique is subsampling the edges of 2-query probabilistically checkable proofs (PCPs), which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth.\n                  <\/jats:p>","DOI":"10.1145\/2818375","type":"journal-article","created":{"date-parts":[[2016,2,8]],"date-time":"2016-02-08T17:37:07Z","timestamp":1454953027000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Label Cover Instances with Large Girth and the Hardness of Approximating Basic\n                    <i>k<\/i>\n                    -Spanner"],"prefix":"10.1145","volume":"12","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Baltimore, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University-Camden, Camden, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/241938.241948"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_5_1","unstructured":"Baruch Awerbuch Alan Baratz and David Peleg. 1992. Efficient Broadcast and Light Weight Spanners. Technical Report CS92-22. Weizman Institute of Science Rehovot Israel."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90038-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496871"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750317"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993680"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993830"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1568639"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646253.683947"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.022"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1266-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.61"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0021-y"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634192"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758846"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1980617.1980629"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367069"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818375","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818375","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:47:13Z","timestamp":1763459233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,31]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2818375"],"URL":"https:\/\/doi.org\/10.1145\/2818375","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,31]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-31","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}