{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:13:14Z","timestamp":1784110394017,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","funder":[{"name":"NSF","award":["CCF-223666"],"award-info":[{"award-number":["CCF-223666"]}]},{"name":"Swiss State Secretariat for Education, Research and Innovation (SERI)","award":["MB22.00054"],"award-info":[{"award-number":["MB22.00054"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718142","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"54-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Asymptotically Optimal Hardness for \ud835\udc58-Set Packing and \ud835\udc58-Matroid Intersection"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1454-7587","authenticated-orcid":false,"given":"Euiwoong","family":"Lee","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Harbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2997-1372","authenticated-orcid":false,"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1150-2386","authenticated-orcid":false,"given":"Theophile","family":"Thiery","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-009-0272-6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/83.3.532"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44985-X_19"},{"key":"e_1_3_2_1_4_1","unstructured":"Piotr Berman and Marek Karpinski. 2003. Improved Approximation Lower Bounds on Small Occurrence Optimization. ECCC."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2005.11.029"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Marek Cygan. 2013. Improved approximation for 3-dimensional matching via bounded pathwidth local search. In SODA. 509\u2013518.","DOI":"10.1109\/FOCS.2013.61"},{"key":"e_1_3_2_1_8_1","volume-title":"TR08-008","author":"Guruswami Venkatesan","year":"2008","unstructured":"Venkatesan Guruswami and Prasad Raghavendra. 2008. Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness. Electron. Colloquium Comput. Complex., TR08-008 (2008), ECCC:TR08-008. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2008\/TR08-008\/index.html"},{"key":"e_1_3_2_1_9_1","unstructured":"Magn\u00fas M. Halld\u00f3rsson. 1995. Approximating Discrete Collections via Local Improvements. In SODA. 160\u2013169."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00032-6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Elad Hazan Shmuel Safra and Oded Schwartz. 2003. On the Complexity of Approximating k-Dimensional Matching. In Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science RANDOM 2003 Princeton NJ USA August 24-26 2003 Proceedings Sanjeev Arora Klaus Jansen Jos\u00e9 D. P. Rolim and Amit Sahai (Eds.) (Lecture Notes in Computer Science Vol. 2764). Springer 83\u201397. https:\/\/doi.org\/10.1007\/978-3-540-45198-3_8 10.1007\/978-3-540-45198-3_8","DOI":"10.1007\/978-3-540-45198-3_8"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0205-6"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_1_16_1","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 42","author":"Khot Subhash","year":"2015","unstructured":"Subhash Khot and Rishi Saket. 2015. Approximating csps using LP relaxation. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 42. 822\u2013833."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.118"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520072"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.71"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/11083232X"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01524-y"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2014.V010A013"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2018.08.007"},{"key":"e_1_3_2_1_24_1","unstructured":"Pasin Manurangsi Preetum Nakkiran and Luca Trevisan. 2015. Near-Optimal UGC-hardness of Approximating Max k-CSP_R. arXiv preprint arXiv:1511.06558."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649606"},{"key":"e_1_3_2_1_26_1","first-page":"1","article-title":"An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs","volume":"187","author":"Neuwohner Meike","year":"2021","unstructured":"Meike Neuwohner. 2021. An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs. In STACS. 187, 53:1\u201353:20.","journal-title":"STACS."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch41"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132519"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch42"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:40:11Z","timestamp":1750693211000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":31,"alternative-id":["10.1145\/3717823.3718142","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718142","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}