{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T22:22:06Z","timestamp":1766442126873,"version":"3.48.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","funder":[{"name":"Italian MUR","award":["PRIN 2022 PNRR project no. P2022HXNSC"],"award-info":[{"award-number":["PRIN 2022 PNRR project no. P2022HXNSC"]}]},{"DOI":"10.13039\/100008536","name":"Amazon Web Services","doi-asserted-by":"publisher","award":["Amazon Research Award for AWS Automated Reasoning on \u201cImplicit Program Analysis\u201d"],"award-info":[{"award-number":["Amazon Research Award for AWS Automated Reasoning on \u201cImplicit Program Analysis\u201d"]}],"id":[{"id":"10.13039\/100008536","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019827","name":"Meta","doi-asserted-by":"publisher","award":["WhatsApp Research Award on \u201cPrivacy-aware Program Analysis\u201d"],"award-info":[{"award-number":["WhatsApp Research Award on \u201cPrivacy-aware Program Analysis\u201d"]}],"id":[{"id":"10.13039\/100019827","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,11,19]]},"DOI":"10.1145\/3719027.3765140","type":"proceedings-article","created":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T23:33:16Z","timestamp":1763854396000},"page":"4439-4453","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact Robustness Certification of k-Nearest Neighbors"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0159-0068","authenticated-orcid":false,"given":"Francesco","family":"Ranzato","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica, University of Padova, Padova, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0018-403X","authenticated-orcid":false,"given":"Ahmad","family":"Shakeel","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, University of Padova, Padova, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6164-6169","authenticated-orcid":false,"given":"Marco","family":"Zanella","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, University of Padova, Padova, Italy"}]}],"member":"320","published-online":{"date-parts":[[2025,11,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_1_1","DOI":"10.1080\/00031305.1992.10475879"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2_1","DOI":"10.1016\/j.biosystems.2018.12.009"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_3_1","DOI":"10.1007\/978-3-642-40994-3_25"},{"key":"e_1_3_2_2_4_1","volume-title":"Proc. 29th Int. Conf. on Machine Learning (ICML'12)","author":"Biggio Battista","year":"2012","unstructured":"Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning attacks against support vector machines. In Proc. 29th Int. Conf. on Machine Learning (ICML'12). Omnipress, 1467\u20131474."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_5_1","DOI":"10.1007\/978-3-030-59013-0_21"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_6_1","DOI":"10.1109\/SP.2017.49"},{"volume-title":"Principles of Abstract Interpretation","author":"Cousot Patrick","unstructured":"Patrick Cousot. 2021. Principles of Abstract Interpretation. MIT Press.","key":"e_1_3_2_2_7_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_8_1","DOI":"10.1145\/512950.512973"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_9_1","DOI":"10.1145\/1014052.1014066"},{"volume-title":"Lili Jiang, Meg Risdal, Nikhil Dandekar, and tomtung.","year":"2017","unstructured":"DataCanary, hilfialkaff, Lili Jiang, Meg Risdal, Nikhil Dandekar, and tomtung. 2017. Quora Question Pairs. https:\/\/kaggle.com\/competitions\/quora-question-pairs.","key":"e_1_3_2_2_10_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_11_1","DOI":"10.1145\/2090236.2090255"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_12_1","DOI":"10.4230\/LIPIcs.ICDT.2022.6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_13_1","DOI":"10.1109\/ICDM58522.2023.00020"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_14_1","DOI":"10.1007\/S10115-024-02108-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_15_1","DOI":"10.1109\/SP.2018.00058"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_16_1","DOI":"10.1007\/978-3-642-02658-4_47"},{"key":"e_1_3_2_2_17_1","volume-title":"Proc. 3rd Int. Conf. on Learning Representations, ICLR","author":"Goodfellow Ian J.","year":"2015","unstructured":"Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and Harnessing Adversarial Examples. In Proc. 3rd Int. Conf. on Learning Representations, ICLR 2015. http:\/\/arxiv.org\/abs\/1412.6572"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_18_1","DOI":"10.1145\/276698.276876"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_19_1","DOI":"10.1609\/aaai.v36i9.21191"},{"key":"e_1_3_2_2_20_1","volume-title":"Nearest Neighbor Machine Translation. In 9th Int. Conf. on Learning Representations, ICLR","author":"Khandelwal Urvashi","year":"2021","unstructured":"Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. 2021. Nearest Neighbor Machine Translation. In 9th Int. Conf. on Learning Representations, ICLR 2021. https:\/\/openreview.net\/forum?id=7wCBOfJ8hJM"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_21_1","DOI":"10.1007\/978-3-642-38652-7_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_22_1","DOI":"10.34727\/2022\/isbn.978-3-85448-053-2_6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_23_1","DOI":"10.1007\/978-3-031-37703-7_16"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_24_1","DOI":"10.1145\/3597926.3598129"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_25_1","DOI":"10.1109\/TPAMI.2018.2889473"},{"volume-title":"Proc. 12th Int. Conf. on Learning Representations, ICLR 2024. https:\/\/openreview.net\/forum?id=h05eQniJsQ","author":"Mao Yuhao","unstructured":"Yuhao Mao, Mark Niklas M\u00fcller, Marc Fischer, and Martin T. Vechev. 2024. Understanding Certified Training with Interval Bound Propagation. In Proc. 12th Int. Conf. on Learning Representations, ICLR 2024. https:\/\/openreview.net\/forum?id=h05eQniJsQ","key":"e_1_3_2_2_26_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_27_1","DOI":"10.1007\/978-3-030-88806-0_15"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_28_1","DOI":"10.1145\/3457607"},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. 35th Int. Conf. on Machine Learning (ICML","author":"Mirman Matthew","year":"2018","unstructured":"Matthew Mirman, Timon Gehr, and Martin T. Vechev. 2018. Differentiable Abstract Interpretation for Provably Robust Neural Networks. In Proc. 35th Int. Conf. on Machine Learning (ICML 2018). 3575-3583. http:\/\/proceedings.mlr.press\/v80\/mirman18b.html"},{"key":"e_1_3_2_2_30_1","volume-title":"Proc. 6th Int. Conf. on Learning Representations, ICLR","author":"Mu Jiaqi","year":"2018","unstructured":"Jiaqi Mu and Pramod Viswanath. 2018. All-but-the-Top: Simple and Effective Postprocessing for Word Representations. In Proc. 6th Int. Conf. on Learning Representations, ICLR 2018. https:\/\/openreview.net\/forum?id=HkuGJ3kCb"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_31_1","DOI":"10.1109\/CVPRW.2017.11"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_32_1","DOI":"10.1201\/9781420035179.CH20"},{"key":"e_1_3_2_2_33_1","volume-title":"Wolsey","author":"Nemhauser George L.","year":"1999","unstructured":"George L. Nemhauser and Laurence A. Wolsey. 1999. Integer and Combinatorial Optimization (2nd ed.). Wiley-Interscience, New York."},{"doi-asserted-by":"publisher","unstructured":"Francesco Ranzato Ahmad Shakeel and Marco Zanella. 2025. tool: a k-NN Certifier. hrefhttps:\/\/doi.org\/10.5281\/zenodo.15205551doi: 10.5281\/zenodo.15205551 hrefhttps:\/\/github.com\/shakehd\/KNN_CertifierGitHub: shakehd\/KNN_Certifier","key":"e_1_3_2_2_34_1","DOI":"10.5281\/zenodo.15205551"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_35_1","DOI":"10.1007\/978-3-030-32304-2_14"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_36_1","DOI":"10.1609\/aaai.v34i04.5998"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_37_1","DOI":"10.18653\/v1\/D19-1410"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_38_1","DOI":"10.18653\/V1\/D19-1410"},{"key":"e_1_3_2_2_39_1","volume-title":"Proc. 34th Annual Conference on Advances in Neural Information Processing Systems, NeurIPS 2020","author":"Ruoss Anian","year":"2020","unstructured":"Anian Ruoss, Mislav Balunovic, Marc Fischer, and Martin Vechev. 2020. Learning Certified Individually Fair Representations. In Proc. 34th Annual Conference on Advances in Neural Information Processing Systems, NeurIPS 2020. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/55d491cf951b1b920900684d71419282-Abstract.html"},{"unstructured":"Lakshay Sharma Laura Graesser Nikita Nangia and Utku Evci. 2019. Natural Language Understanding with the Quora Question Pairs Dataset. arXiv preprint arXiv:1907.01041. http:\/\/arxiv.org\/abs\/1907.01041","key":"e_1_3_2_2_40_1"},{"key":"e_1_3_2_2_41_1","volume-title":"Proc. Annual Conf. on Neural Information Processing Systems, NeurIPS","author":"Singh Gagandeep","year":"2018","unstructured":"Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus P\u00fcschel, and Martin T. Vechev. 2018. Fast and Effective Robustness Certification. In Proc. Annual Conf. on Neural Information Processing Systems, NeurIPS 2018. 10825-10836. http:\/\/papers.nips.cc\/paper\/8278-fast-and-effective-robustness-certification"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_42_1","DOI":"10.1145\/3290354"},{"key":"e_1_3_2_2_43_1","volume-title":"Proc. Annual Conf. on Neural Information Processing Systems, NeurIPS 2021","author":"Sitawarin Chawin","year":"2021","unstructured":"Chawin Sitawarin, Evgenios M. Kornaropoulos, Dawn Song, and David A. Wagner. 2021. Adversarial Examples for k-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams. In Proc. Annual Conf. on Neural Information Processing Systems, NeurIPS 2021. 15486-15497. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/82ca5dd156cc926b2992f73c2896f761-Abstract.html"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_44_1","DOI":"10.1109\/SPW50608.2020.00023"},{"key":"e_1_3_2_2_45_1","volume-title":"Proc. 2nd Int. Conf. on Learning Representations, ICLR","author":"Szegedy Christian","year":"2014","unstructured":"Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In Proc. 2nd Int. Conf. on Learning Representations, ICLR 2014. http:\/\/arxiv.org\/abs\/1312.6199"},{"key":"e_1_3_2_2_46_1","volume-title":"Augmented SBERT: Data augmentation method for improving bi-encoders for pairwise sentence scoring tasks. arXiv preprint arXiv:2010.08240","author":"Thakur Nandan","year":"2020","unstructured":"Nandan Thakur, Nils Reimers, Johannes Daxenberger, and Iryna Gurevych. 2020. Augmented SBERT: Data augmentation method for improving bi-encoders for pairwise sentence scoring tasks. arXiv preprint arXiv:2010.08240 (2020)."},{"key":"e_1_3_2_2_47_1","volume-title":"A Review of Formal Methods applied to Machine Learning. CoRR","author":"Urban Caterina","year":"2021","unstructured":"Caterina Urban and Antoine Min\u00e9. 2021. A Review of Formal Methods applied to Machine Learning. CoRR, Vol. abs\/2104.02466 (2021). https:\/\/arxiv.org\/abs\/2104.02466"},{"doi-asserted-by":"publisher","unstructured":"Lu Wang Xuanqing Liu Jinfeng Yi Zhi-Hua Zhou and Cho-Jui Hsieh. 2019. Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspective. doi:10.48550\/ARXIV.1906.03972","key":"e_1_3_2_2_48_1","DOI":"10.48550\/ARXIV.1906.03972"},{"key":"e_1_3_2_2_49_1","volume-title":"Proc. Annual Conf. on Neural Information Processing Systems 2020","author":"Wang Wenhui","year":"2020","unstructured":"Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020. MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers. In Proc. Annual Conf. on Neural Information Processing Systems 2020, NeurIPS 2020. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html"},{"key":"e_1_3_2_2_50_1","volume-title":"Proc. 35th Int. Conf. on Machine Learning, ICML 2018 (PMLR","volume":"5129","author":"Wang Yizhen","year":"2018","unstructured":"Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. 2018. Analyzing the Robustness of Nearest Neighbors to Adversarial Examples. In Proc. 35th Int. Conf. on Machine Learning, ICML 2018 (PMLR, Vol. 80). 5120-5129. http:\/\/proceedings.mlr.press\/v80\/wang18c.html"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_51_1","DOI":"10.1007\/S10115-007-0114-2"},{"key":"e_1_3_2_2_52_1","volume-title":"Proc. 23rd Int. Conf. on Artificial Intelligence and Statistics, AISTATS 2020 (PMLR","volume":"951","author":"Yang Yao-Yuan","year":"2020","unstructured":"Yao-Yuan Yang, Cyrus Rashtchian, Yizhen Wang, and Kamalika Chaudhuri. 2020. Robustness for Non-Parametric Classification: A Generic Attack and Defense. In Proc. 23rd Int. Conf. on Artificial Intelligence and Statistics, AISTATS 2020 (PMLR, Vol. 108). 941-951. http:\/\/proceedings.mlr.press\/v108\/yang20b.html"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_53_1","DOI":"10.1109\/ACCESS.2019.2944253"},{"key":"e_1_3_2_2_54_1","volume-title":"Proc. 8th Int. Conf. on Learning Representations, ICLR","author":"Zhang Huan","year":"2020","unstructured":"Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane S. Boning, and Cho-Jui Hsieh. 2020. Towards Stable and Efficient Training of Verifiably Robust Neural Networks. In Proc. 8th Int. Conf. on Learning Representations, ICLR 2020. https:\/\/openreview.net\/forum?id=Skxuk1rFwB"}],"event":{"sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"],"acronym":"CCS '25","name":"CCS '25: ACM SIGSAC Conference on Computer and Communications Security","location":"Taipei Taiwan"},"container-title":["Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3719027.3765140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T22:18:14Z","timestamp":1766441894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3719027.3765140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,19]]},"references-count":54,"alternative-id":["10.1145\/3719027.3765140","10.1145\/3719027"],"URL":"https:\/\/doi.org\/10.1145\/3719027.3765140","relation":{},"subject":[],"published":{"date-parts":[[2025,11,19]]},"assertion":[{"value":"2025-11-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}