乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:17:47Z","timestamp":1740143867915,"version":"3.37.3"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,12,31]],"date-time":"2016-12-31T00:00:00Z","timestamp":1483142400000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["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"],"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"],"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":"\n We study the well-known\n 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 k<\/jats:italic>\n , the problem is roughly 2\n \n log\n 1-\u03f5<\/jats:sup>\n n)\/k<\/jats:italic>\n <\/jats:sup>\n hard to approximate for all constant \u03f5 > 0. A similar theorem was claimed by Elkin and Peleg [2000] as part of an attempt to prove hardness for the basic\n k<\/jats:italic>\n -spanner problem, but their proof was later found to have a fundamental error. Thus, we give both\n 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 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 NP<\/jats:italic>\n \u2286\n BPTIME<\/jats:italic>\n (2\n \n polylog(n)<\/jats:italic>\n <\/jats:sup>\n , we show (roughly) that for every\n k<\/jats:italic>\n \u2a7e 3 and every constant \u03f5 > 0, it is hard to approximate the basic\n k<\/jats:italic>\n -spanner problem within a factor better than 2\n \n log\n 1-\u03f5<\/jats:sup>\n n)\/k<\/jats:italic>\n <\/jats:sup>\n . This improves over the previous best lower bound of only \u03a9(log\n n<\/jats:italic>\n )\/\n 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-08T22:37:07Z","timestamp":1454971027000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Label Cover Instances with Large Girth and the Hardness of Approximating Basic\n k<\/i>\n -Spanner"],"prefix":"10.1145","volume":"12","author":[{"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Baltimore, MD"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[{"name":"Rutgers University-Camden, Camden, NJ"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2015,12,31]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1007\/BF02189308"},{"volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Carsten Lund . 1997. Hardness of approximations . In Approximation Algorithms for NP-Hard Problems , D. Hochbaum (Ed.). PWS Publishing , Boston, MA , 399--446. Sanjeev Arora and Carsten Lund. 1997. Hardness of approximations. In Approximation Algorithms for NP-Hard Problems, D. Hochbaum (Ed.). PWS Publishing, Boston, MA, 399--446.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/278298.278306"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/273865.273901"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/0196-8858(86)90038-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1198513.1198518"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"e_1_2_1_9_1","volume-title":"Woodruff","author":"Bhattacharyya Arnab","year":"2009","unstructured":"Arnab Bhattacharyya , Elena Grigorescu , Kyomin Jung , Sofya Raskhodnikova , and David P . Woodruff . 2009 . Transitive-closure spanners. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909). 932--941. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. 2009. Transitive-closure spanners. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909). 932--941."},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/090750317"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1137\/S0097539794261295"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/331605.331610"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1006\/jagm.2000.1134"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1016\/j.jalgor.2003.08.001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1993636.1993680"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1993806.1993830"},{"volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"Dubhashi Devdatt","unstructured":"Devdatt Dubhashi and Alessandro Panconesi . 2009. Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge University Press , New York, NY . Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY.","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/1103963.1103968"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.5555\/646253.683947"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1016\/j.tcs.2004.11.022"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1007\/s00224-006-1266-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1145\/285055.285059"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1006\/jcss.1998.1587"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1137\/070683155"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/1162349.1162351"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/502090.502098"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1109\/SFCS.2005.61"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1007\/s00453-001-0021-y"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1006\/jagm.1994.1032"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.5555\/2634074.2634192"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1007\/BF01758846"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/185675.306789"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1002\/jgt.3190130114"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1137\/0218050"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_36_1","volume-title":"Transitive-closure spanners: A survey","author":"Raskhodnikova Sofya","year":"1986","unstructured":"Sofya Raskhodnikova . 2010. Transitive-closure spanners: A survey . In Property Testing, O. Goldreich (Ed.). Springer-Verlag , Berlin, Germany , 167--196. http:\/\/dl.acm.org\/citation.cfm?id= 1986 603.1986615. Sofya Raskhodnikova. 2010. Transitive-closure spanners: A survey. In Property Testing, O. Goldreich (Ed.). Springer-Verlag, Berlin, Germany, 167--196. http:\/\/dl.acm.org\/citation.cfm?id=1986603.1986615."},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1137\/S0097539795280895"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/1367064.1367069"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/378580.378581"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/1044731.1044732"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"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":[[2022,12,31]],"date-time":"2022-12-31T10:43:30Z","timestamp":1672483410000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,31]]},"references-count":39,"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":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"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":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}