{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:53Z","timestamp":1781031413478,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100006502","name":"Defense Sciences Office, DARPA","doi-asserted-by":"publisher","award":["HR00112020023"],"award-info":[{"award-number":["HR00112020023"]}],"id":[{"id":"10.13039\/100006502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2023-05006"],"award-info":[{"award-number":["RGPIN-2023-05006"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101019547"],"award-info":[{"award-number":["101019547"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DGE-2141064"],"award-info":[{"award-number":["DGE-2141064"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS-2154149"],"award-info":[{"award-number":["CNS-2154149"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800741","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"210-221","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Adaptive Robustness of Hypergrid Johnson-Lindenstrauss"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0338-6151","authenticated-orcid":false,"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[{"name":"University of Ottawa, Ottawa, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3021-7150","authenticated-orcid":false,"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[{"name":"Bocconi University, Milan, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0555-4200","authenticated-orcid":false,"given":"Neekon","family":"Vafa","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2666-0045","authenticated-orcid":false,"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Emmanuel Abbe Shuangping Li and Allan Sly. 2021. Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron. arxiv:2102.13069. arxiv:2102.13069"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519975"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-024-01259-8"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/ab227a"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/ab99be"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/RSA.20955"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/ad3a4a"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520064"},{"key":"e_1_3_2_1_11_1","unstructured":"Omri Ben-Eliezer Esty Kelman Uri Meir and Sofya Raskhodnikova. 2023. Property Testing with Online Adversaries. arxiv:2311.16566. arxiv:2311.16566"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.28"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2504.09331"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2019.16"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488680"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451000"},{"key":"e_1_3_2_1_18_1","volume-title":"International Conference on Machine Learning, ICML 2022","volume":"4140","author":"Cohen Edith","year":"2022","unstructured":"Edith Cohen, Xin Lyu, Jelani Nelson, Tam\u00e1s Sarl\u00f3s, Moshe Shechner, and Uri Stemmer. 2022. On the Robustness of CountSketch to Adaptive Inputs. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv\u00e1ri, Gang Niu, and Sivan Sabato (Eds.) (Proceedings of Machine Learning Research, Vol. 162). PMLR, 4112\u20134140. https:\/\/proceedings.mlr.press\/v162\/cohen22a.html"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2411.06370"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.05723"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/OASICS.SOSA.2018.15"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545476"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2108492118"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00061"},{"key":"e_1_3_2_1_25_1","volume-title":"Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023","volume":"3263","author":"Gamarnik David","year":"2023","unstructured":"David Gamarnik, Eren C. Kizildag, Will Perkins, and Changji Xu. 2023. Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, 3231\u20133263. https:\/\/proceedings.mlr.press\/v195\/gamarnik23a.html"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00093"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00136"},{"key":"e_1_3_2_1_28_1","volume-title":"To appear at STOC 2025","author":"Gribelyuk Elena","unstructured":"Elena Gribelyuk, Honghao Lin, David P Woodruff, Huacheng Yu, and Samson Zhou. 2025. Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. arXiv preprint arXiv:2503.19629, To appear at STOC 2025"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00112"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488624"},{"key":"e_1_3_2_1_31_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Hassidim Avinatan","year":"2020","unstructured":"Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/0172d289da48c48de8c5ebf3de9f7ee1-Abstract.html"},{"key":"e_1_3_2_1_32_1","unstructured":"Hugging Face. 2023. Semantic search with FAISS. https:\/\/huggingface.co\/learn\/nlp-course\/ chapter5\/6?fw=tf"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/22-AAP1784"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.94"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2016.82"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.64"},{"key":"e_1_3_2_1_39_1","volume-title":"1st International Conference on Learning Representations, ICLR","author":"Mikolov Tom\u00e1s","year":"2013","unstructured":"Tom\u00e1s Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient Estimation of Word Representations in Vector Space. In 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). arxiv:1301.3781"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374471"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384319"},{"key":"e_1_3_2_1_42_1","volume-title":"MTEB: Massive Text Embedding Benchmark. arxiv:2210.07316. arxiv:2210.07316","author":"Muennighoff Niklas","year":"2023","unstructured":"Niklas Muennighoff, Nouamane Tazi, Lo\u00efc Magne, and Nils Reimers. 2023. MTEB: Massive Text Embedding Benchmark. arxiv:2210.07316. arxiv:2210.07316"},{"key":"e_1_3_2_1_43_1","unstructured":"Moni Naor and Eylon Yogev. 2019. Bloom Filters in Adversarial Environments. arxiv:1412.8356. arxiv:1412.8356"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316307"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-1120"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451119"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2208.09493"},{"key":"e_1_3_2_1_48_1","volume-title":"Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.","author":"Radford Alec","year":"2021","unstructured":"Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021. Learning Transferable Visual Models From Natural Language Supervision. arxiv:2103.00020. arxiv:2103.00020"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_1_50_1","volume-title":"Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. CoRR, abs\/1908.10084","author":"Reimers Nils","year":"2019","unstructured":"Nils Reimers and Iryna Gurevych. 2019. Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. CoRR, abs\/1908.10084 (2019), arXiv:1908.10084. arxiv:1908.10084"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0054137"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.18653\/V1\/2020.EMNLP-MAIN.344"},{"key":"e_1_3_2_1_53_1","volume-title":"Mass-Producing Failures of Multimodal Systems with Language Models. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023","author":"Tong Shengbang","year":"2023","unstructured":"Shengbang Tong, Erik Jones, and Jacob Steinhardt. 2023. Mass-Producing Failures of Multimodal Systems with Language Models. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (Eds.). http:\/\/papers.nips.cc\/paper_files\/paper\/2023\/hash\/5d570ed1708bbe19cb60f7a7aff60575-Abstract-Conference.html"},{"key":"e_1_3_2_1_54_1","volume-title":"Number Partitioning and Lattices. IACR Cryptol. ePrint Arch., 130. https:\/\/eprint.iacr.org\/2025\/130 To appear at STOC 2025","author":"Vafa Neekon","unstructured":"Neekon Vafa and Vinod Vaikuntanathan. 2025. Symmetric Perceptrons, Number Partitioning and Lattices. IACR Cryptol. ePrint Arch., 130. https:\/\/eprint.iacr.org\/2025\/130 To appear at STOC 2025"},{"key":"e_1_3_2_1_55_1","volume-title":"Adversarial Illusions in Multi-Modal Embeddings. In 33rd USENIX Security Symposium, USENIX Security 2024","author":"Zhang Tingwei","year":"2024","unstructured":"Tingwei Zhang, Rishi D. Jha, Eugene Bagdasaryan, and Vitaly Shmatikov. 2024. Adversarial Illusions in Multi-Modal Embeddings. In 33rd USENIX Security Symposium, USENIX Security 2024, Philadelphia, PA, USA, August 14-16, 2024, Davide Balzarotti and Wenyuan Xu (Eds.). USENIX Association. https:\/\/www.usenix.org\/conference\/usenixsecurity24\/presentation\/zhang-tingwei"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800741","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:57:32Z","timestamp":1781027852000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":55,"alternative-id":["10.1145\/3798129.3800741","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800741","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}