{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:06:25Z","timestamp":1749873985193,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":9,"publisher":"ACM","funder":[{"name":"Australian Research Council","award":["DE230101329"],"award-info":[{"award-number":["DE230101329"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733515","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"372-374","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Brief Announcement: Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7153-5211","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Canonne","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5291-126X","authenticated-orcid":false,"given":"Yun","family":"Li","sequence":"additional","affiliation":[{"name":"University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6984-4007","authenticated-orcid":false,"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Melbourne, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Space-efficient local computation algorithms","author":"Alon Noga","unstructured":"Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. 2012. Space-efficient local computation algorithms. In SODA. SIAM, 1132\u20131139."},{"key":"e_1_3_2_1_2_1","volume-title":"Local Computation Algorithms for Maximum Matching: New Lower Bounds","author":"Behnezhad Soheil","unstructured":"Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. 2023. Local Computation Algorithms for Maximum Matching: New Lower Bounds. In FOCS. IEEE, 2322\u20132335."},{"key":"e_1_3_2_1_3_1","volume-title":"Average-Case Local Computation Algorithms. CoRR abs\/2403.00129","author":"Biswas Amartya Shankha","year":"2024","unstructured":"Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, and Ronitt Rubinfeld. 2024. Average-Case Local Computation Algorithms. CoRR abs\/2403.00129 (2024)."},{"key":"e_1_3_2_1_4_1","unstructured":"Cl\u00e9ment L. Canonne Yun Li and Seeun William Umboh. 2025. Local Computation Algorithms for Knapsack: impossibility results and how to avoid them. arXiv:2504.01543 [cs.DS] https:\/\/arxiv.org\/abs\/2504.01543 Full version of this paper."},{"key":"e_1_3_2_1_5_1","volume-title":"Local Computation of Maximal Independent Set","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari. 2022. Local Computation of Maximal Independent Set. In FOCS. IEEE, 438\u2013449."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29952-0_17"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0126-y"},{"key":"e_1_3_2_1_9_1","volume-title":"Innovations in Computer Science - ICS","author":"Rubinfeld Ronitt","year":"2011","unstructured":"Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. 2011. Fast Local Computation Algorithms. In Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7\u20139, 2011. Proceedings, Bernard Chazelle (Ed.). Tsinghua University Press, 223\u2013238."}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:24:45Z","timestamp":1749824685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":9,"alternative-id":["10.1145\/3732772.3733515","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733515","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}