[{"alternative_title":["ISTA Master’s Thesis"],"keyword":["Privacy-preserving verification","Runtime verification","Monitoring","Reactive functionalities","Cryptographic protocols"],"fulldoi":"https://doi.org/10.15479/AT-ISTA-21401","publisher":"Institute of Science and Technology Austria","year":"2026","month":"03","date_updated":"2026-03-13T13:37:20Z","file_date_updated":"2026-03-10T15:20:09Z","file":[{"date_created":"2026-03-06T14:06:25Z","content_type":"application/pdf","creator":"mkarimi","file_id":"21404","file_name":"2026_Karimi_Mahyar_Thesis.pdf","relation":"main_file","access_level":"open_access","date_updated":"2026-03-10T15:20:09Z","checksum":"3f49f05c9d123e14d7adb73d3bc50fe2","file_size":766048},{"date_created":"2026-03-06T14:06:25Z","file_name":"2026_Karimi_Mahyar_Thesis_src.zip","relation":"source_file","file_id":"21405","creator":"mkarimi","content_type":"application/zip","date_updated":"2026-03-06T14:06:25Z","access_level":"closed","checksum":"8fb9db4b4187e26443369a993427a5ff","file_size":1243394}],"has_accepted_license":"1","oa":1,"ddc":["000"],"language":[{"iso":"eng"}],"_id":"21401","supervisor":[{"last_name":"Henzinger","orcid":"0000-0002-2985-7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"}],"page":"60","author":[{"first_name":"Mahyar","id":"6e5417ba-5355-11ee-ae5a-94c2e510b26b","orcid":"0009-0005-0820-1696","last_name":"Karimi","full_name":"Karimi, Mahyar"}],"department":[{"_id":"GradSch"},{"_id":"ToHe"}],"abstract":[{"lang":"eng","text":"Runtime verification offers scalable solutions to improve the safety and reliability of systems. However, systems that require verification or monitoring by a third party to ensure compliance with a specification might contain sensitive information, causing privacy concerns when usual runtime verification approaches are used. Privacy is compromised if protected information about the system, or sensitive data that is processed by the system, is revealed. In addition, revealing the specification being monitored may undermine the essence of third-party verification.\r\n\r\nIn this thesis, we propose a protocol for privacy-preserving runtime verification of systems against formal sequential specifications. We develop the protocol in two steps. In the first step, the monitor verifies whether the system satisfies the specification without learning anything else, though both parties are aware of the specification. In the second step, we extend the protocol to ensure that the system remains oblivious to the monitored specification, while the monitor learns only whether the system satisfies the specification and nothing more. Our protocol adapts and improves existing techniques used in cryptography, and more specifically, multi-party computation.\r\n\r\nThe sequential specification defines the observation step of the monitor, whose granularity depends on the situation (e.g., banks may be monitored on a daily basis). Our protocol exchanges a single message per observation step, after an initialization phase. This design minimizes communication overhead, enabling relatively lightweight privacy-preserving monitoring. We implement our approach for monitoring specifications described by register automata and evaluate it experimentally.\r\n"}],"article_processing_charge":"No","doi":"10.15479/AT-ISTA-21401","day":"05","date_created":"2026-03-05T15:20:47Z","corr_author":"1","type":"dissertation","related_material":{"record":[{"id":"21020","relation":"part_of_dissertation","status":"public"}]},"acknowledgement":"This work is part of the project VAMOS, which has received funding from the European\r\nResearch Council (ERC) under grant agreement No. 101020093, and the Austrian Science\r\nFund (FWF) SFB project SpyCoDe F8502.\r\n","citation":{"chicago":"Karimi, Mahyar. “Privacy-Preserving Runtime Verification.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-21401\">https://doi.org/10.15479/AT-ISTA-21401</a>.","mla":"Karimi, Mahyar. <i>Privacy-Preserving Runtime Verification</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21401\">10.15479/AT-ISTA-21401</a>.","ama":"Karimi M. Privacy-preserving runtime verification. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21401\">10.15479/AT-ISTA-21401</a>","ieee":"M. Karimi, “Privacy-preserving runtime verification,” Institute of Science and Technology Austria, 2026.","ista":"Karimi M. 2026. Privacy-preserving runtime verification. Institute of Science and Technology Austria.","short":"M. Karimi, Privacy-Preserving Runtime Verification, Institute of Science and Technology Austria, 2026.","apa":"Karimi, M. (2026). <i>Privacy-preserving runtime verification</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-21401\">https://doi.org/10.15479/AT-ISTA-21401</a>"},"project":[{"name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","call_identifier":"H2020"},{"name":"Security and Privacy by Design for Complex Systems","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f","grant_number":"F8512"}],"status":"public","publication_status":"published","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","OA_place":"repository","publication_identifier":{"issn":["2791-4585"]},"date_published":"2026-03-05T00:00:00Z","oa_version":"Published Version","title":"Privacy-preserving runtime verification","ec_funded":1,"degree_awarded":"MS"},{"author":[{"full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","last_name":"Safavi Hemami"},{"full_name":"Vadhan, Salil","first_name":"Salil","last_name":"Vadhan"}],"page":"1-26","researchdata_availability":"no","article_processing_charge":"Yes","department":[{"_id":"MoHe"}],"abstract":[{"lang":"eng","text":"Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously\r\nover a long period of time, making more statistical releases as either queries come in or the dataset is updated.\r\nIn this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion\r\nof neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries\r\nand dataset updates to the different composed mechanisms. Previous concurrent composition theorems for\r\ndifferential privacy were only for the case when the dataset is static, with no adaptive updates. We also give\r\nthe first interactive and continual generalizations of the “parallel composition theorem” for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem\r\nholds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential privacy, but it fails to hold for composing approximately differentially private mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent\r\nfilter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.\r\nWe then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition\r\ntheorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.\r\nWe also provide a framework that simplifies the analysis of local differential privacy when the protocol\r\nincludes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5]."}],"doi":"10.1145/3801895","ddc":["000"],"oa":1,"intvolume":"         4","has_accepted_license":"1","language":[{"iso":"eng"}],"das_tickbox":"0","external_id":{"arxiv":["2411.03299"]},"_id":"22318","issue":"2","date_updated":"2026-07-16T09:14:49Z","file_date_updated":"2026-07-16T09:09:53Z","file":[{"date_updated":"2026-07-16T09:09:53Z","access_level":"open_access","checksum":"c6c5e256d02b90682c0690c3bee94040","file_size":655405,"date_created":"2026-07-16T09:09:53Z","success":1,"relation":"main_file","file_name":"2026_ACMMgmtData_Henzinger.pdf","content_type":"application/pdf","file_id":"22345","creator":"dernst"}],"fulldoi":"https://doi.org/10.1145/3801895","supplementarymaterial":"no","keyword":["differential privacy","concurrent composition","continual release","continual observation","data streaming","continual mechanisms","concurrent parallel composition","concurrent filter composition"],"year":"2026","month":"06","publisher":"Association for Computing Machinery","volume":4,"quality_controlled":"1","PlanS_conform":"1","date_published":"2026-06-01T00:00:00Z","ec_funded":1,"oa_version":"Published Version","title":"Concurrent composition for differentially private continual mechanisms","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the ACM on Management of Data","status":"public","OA_place":"publisher","OA_type":"gold","publication_identifier":{"issn":["2836-6573"]},"acknowledgement":"1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi were supported by the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564), and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982, and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic copyright license to any author-accepted manuscript version arising from this submission.\r\nViews and opinions expressed are however those of the author(s)\r\nonly and do not necessarily reflect those of the European Union\r\nor the European Research Council Executive Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible for them.","citation":{"short":"M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26.","apa":"Henzinger, M., Safavi Hemami, R., &#38; Vadhan, S. (2026). Concurrent composition for differentially private continual mechanisms. <i>Proceedings of the ACM on Management of Data</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3801895\">https://doi.org/10.1145/3801895</a>","ieee":"M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for differentially private continual mechanisms,” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026.","ista":"Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2), 1–26.","ama":"Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially private continual mechanisms. <i>Proceedings of the ACM on Management of Data</i>. 2026;4(2):1-26. doi:<a href=\"https://doi.org/10.1145/3801895\">10.1145/3801895</a>","chicago":"Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent Composition for Differentially Private Continual Mechanisms.” <i>Proceedings of the ACM on Management of Data</i>. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3801895\">https://doi.org/10.1145/3801895</a>.","mla":"Henzinger, Monika, et al. “Concurrent Composition for Differentially Private Continual Mechanisms.” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:<a href=\"https://doi.org/10.1145/3801895\">10.1145/3801895</a>."},"project":[{"call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"}],"date_created":"2026-07-13T14:59:14Z","scopus_import":"1","day":"01","arxiv":1,"article_type":"original","corr_author":"1","type":"journal_article","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"}},{"citation":{"ieee":"N. Kalinin and J. D. Andersson, “Learning rate scheduling with matrix factorization for private training,” in <i>7th Symposium on Foundations of Responsible Computing</i>, Cambridge, MA; United States, 2026, vol. 368.","ista":"Kalinin N, Andersson JD. 2026. Learning rate scheduling with matrix factorization for private training. 7th Symposium on Foundations of Responsible Computing. FORC: Symposium on Foundations of Responsible Computing, LIPIcs, vol. 368, 2:1-2:21.","short":"N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","apa":"Kalinin, N., &#38; Andersson, J. D. (2026). Learning rate scheduling with matrix factorization for private training. In <i>7th Symposium on Foundations of Responsible Computing</i> (Vol. 368). Cambridge, MA; United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">https://doi.org/10.4230/LIPIcs.FORC.2026.2</a>","chicago":"Kalinin, Nikita, and Joel D Andersson. “Learning Rate Scheduling with Matrix Factorization for Private Training.” In <i>7th Symposium on Foundations of Responsible Computing</i>, Vol. 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">https://doi.org/10.4230/LIPIcs.FORC.2026.2</a>.","mla":"Kalinin, Nikita, and Joel D. Andersson. “Learning Rate Scheduling with Matrix Factorization for Private Training.” <i>7th Symposium on Foundations of Responsible Computing</i>, vol. 368, 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">10.4230/LIPIcs.FORC.2026.2</a>.","ama":"Kalinin N, Andersson JD. Learning rate scheduling with matrix factorization for private training. In: <i>7th Symposium on Foundations of Responsible Computing</i>. Vol 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">10.4230/LIPIcs.FORC.2026.2</a>"},"project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020"},{"_id":"d8f03aaa-b035-11f1-8588-d5147fa879e0","grant_number":"COE12","name":"Bilateral Artificial Intelligence (Lampert)"}],"acknowledgement":"We thank Rasmus Pagh, Christoph Lampert and Jalaj Upadhyay for valuable\r\ncomments on an early draft. We thank Ryan Mckenna for a fruitful discussion on the experiment\r\ndesign. We thank Antti Honkela for sharing insights on learning rate scheduling and DP.\r\nNikita P. Kalinin: Funded in part by the Austrian Science Fund (FWF) [10.55776/COE12].\r\nJoel Daniel Andersson: Funded by the European Union. Views and opinions expressed are however\r\nthose of the author(s) only and do not necessarily reflect those of the European Union or the European\r\nResearch Council Executive Agency. Neither the European Union nor the granting authority can be\r\nheld responsible for them. This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564). Additional funding by Providentia, a Data Science Distinguished Investigator grant\r\nfrom Novo Nordisk Fonden, with additional support from VILLUM Investigator grant 54451.\r\n","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"type":"conference","arxiv":1,"scopus_import":"1","date_created":"2026-06-28T22:01:34Z","day":"01","corr_author":"1","date_published":"2026-06-01T00:00:00Z","oa_version":"Published Version","title":"Learning rate scheduling with matrix factorization for private training","article_number":"2:1-2:21","ec_funded":1,"quality_controlled":"1","conference":{"start_date":"2026-06-03","name":"FORC: Symposium on Foundations of Responsible Computing","end_date":"2026-06-05","location":"Cambridge, MA; United States"},"publication_identifier":{"isbn":["9783959774192"],"eissn":["1868-8969"]},"status":"public","publication_status":"published","publication":"7th Symposium on Foundations of Responsible Computing","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"gold","OA_place":"publisher","file_date_updated":"2026-06-29T06:55:23Z","file":[{"creator":"dernst","file_id":"22149","content_type":"application/pdf","file_name":"2026_LIPIcsFORC_Kalinin.pdf","relation":"main_file","success":1,"date_created":"2026-06-29T06:55:23Z","file_size":1231914,"checksum":"c661f016d3861a1c1b590b87a744d087","access_level":"open_access","date_updated":"2026-06-29T06:55:23Z"}],"date_updated":"2026-09-16T07:37:21Z","alternative_title":["LIPIcs"],"keyword":["differential privacy","machine learning","matrix factorization"],"fulldoi":"https://doi.org/10.4230/LIPIcs.FORC.2026.2","supplementarymaterial":"no","volume":368,"year":"2026","month":"06","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"ChLa"},{"_id":"GradSch"},{"_id":"MoHe"}],"abstract":[{"lang":"eng","text":"We study differentially private model training with stochastic gradient descent under learning rate scheduling and correlated noise. Although correlated noise, in particular via matrix factorizations, has been shown to improve accuracy, prior theoretical work focused primarily on the prefix-sum workload. That workload assumes a constant learning rate, whereas in practice learning rate schedules are widely used to accelerate training and improve convergence. We close this gap by deriving general upper and lower bounds for a broad class of learning rate schedules in both single- and multi-epoch settings. Building on these results, we propose a learning-rate-aware factorization that achieves improvements over prefix-sum factorizations under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient constructions suitable for practical deployment, and experiments on CIFAR-10 and IMDB datasets confirm that schedule-aware factorizations improve accuracy in private training."}],"researchdata_availability":"no","article_processing_charge":"No","doi":"10.4230/LIPIcs.FORC.2026.2","author":[{"first_name":"Nikita","id":"4b14526e-14d2-11ed-ba64-c14c9553d137","last_name":"Kalinin","full_name":"Kalinin, Nikita"},{"full_name":"Andersson, Joel D","last_name":"Andersson","id":"4a893819-d954-11f0-89b1-e360bad9ccc5","first_name":"Joel D"}],"_id":"22146","oa":1,"has_accepted_license":"1","intvolume":"       368","ddc":["000"],"external_id":{"arxiv":["2511.17994"]},"language":[{"iso":"eng"}],"das_tickbox":"0"},{"keyword":["Static Program Analysis","Differential Privacy","Probabilistic Programming","Martingales"],"supplementarymaterial":"no","fulldoi":"https://doi.org/10.1145/3808296","volume":10,"publisher":"ACM","year":"2026","month":"06","file_date_updated":"2026-06-24T06:19:56Z","file":[{"date_updated":"2026-06-24T06:19:56Z","access_level":"open_access","checksum":"994bf21d6269dabccf1e1091e02962c5","file_size":858595,"date_created":"2026-06-24T06:19:56Z","relation":"main_file","file_name":"2026_ProcACMProgrammingLanguages_Chatterjee.pdf","success":1,"creator":"dernst","file_id":"22135","content_type":"application/pdf"}],"date_updated":"2026-09-16T07:36:14Z","_id":"22102","issue":"PLDI","intvolume":"        10","has_accepted_license":"1","oa":1,"ddc":["000"],"external_id":{"arxiv":["2603.26215"]},"language":[{"iso":"eng"}],"das_tickbox":"1","abstract":[{"text":"Differential privacy (DP) has established itself as one of the standards for ensuring privacy of individual data. However, reasoning about DP is a challenging and error-prone task, hence methods for formal verification and refutation of DP properties have received significant interest in recent years. In this work, we present a novel method for automated formal refutation of є-DP. Our method refutes є-DP by searching for a pair of inputs together with a non-negative function over outputs whose expected value on these two inputs differs by a significant amount. The two inputs and the non-negative function over outputs are computed simultaneously, by utilizing upper expectation supermartingales and lower expectation submartingales from probabilistic program analysis, which we leverage to introduce a sound and complete proof rule for є-DP refutation. To the best of our knowledge, our method is the first method for є-DP refutation to offer the following four desirable features: (1) it is fully automated, (2) it is applicable to stochastic mechanisms with sampling instructions from both discrete and continuous distributions, (3) it provides soundness guarantees, and (4) it provides semi-completeness guarantees. Our experiments show that our prototype tool SuperDP achieves superior performance compared to the state of the art and manages to refute є-DP for a number of challenging examples collected from the literature, including ones that were out of the reach of prior methods.","lang":"eng"}],"department":[{"_id":"KrCh"}],"researchdata_availability":"yes","article_processing_charge":"Yes","doi":"10.1145/3808296","dataavailabilitystatement":"The artifact supporting the findings of this study, which includes the underlying datasets, software\r\ncode, and experiments, is publicly available in Zenodo https://zenodo.org/records/19399862.","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Kafshdar Goharshadi","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","first_name":"Ehsan","orcid":"0000-0002-8595-0587","full_name":"Kafshdar Goharshadi, Ehsan"},{"full_name":"Zikelic, Dorde","first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","last_name":"Zikelic"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"type":"journal_article","article_type":"original","arxiv":1,"scopus_import":"1","day":"08","date_created":"2026-06-21T22:02:59Z","corr_author":"1","citation":{"ista":"Chatterjee K, Goharshady E, Zikelic D. 2026. SuperDP: Differential privacy refutation via supermartingales. Proceedings of the ACM on Programming Languages. 10(PLDI), 218.","ieee":"K. Chatterjee, E. Goharshady, and D. Zikelic, “SuperDP: Differential privacy refutation via supermartingales,” <i>Proceedings of the ACM on Programming Languages</i>, vol. 10, no. PLDI. ACM, 2026.","apa":"Chatterjee, K., Goharshady, E., &#38; Zikelic, D. (2026). SuperDP: Differential privacy refutation via supermartingales. <i>Proceedings of the ACM on Programming Languages</i>. ACM. <a href=\"https://doi.org/10.1145/3808296\">https://doi.org/10.1145/3808296</a>","short":"K. Chatterjee, E. Goharshady, D. Zikelic, Proceedings of the ACM on Programming Languages 10 (2026).","mla":"Chatterjee, Krishnendu, et al. “SuperDP: Differential Privacy Refutation via Supermartingales.” <i>Proceedings of the ACM on Programming Languages</i>, vol. 10, no. PLDI, 218, ACM, 2026, doi:<a href=\"https://doi.org/10.1145/3808296\">10.1145/3808296</a>.","chicago":"Chatterjee, Krishnendu, Ehsan Goharshady, and Dorde Zikelic. “SuperDP: Differential Privacy Refutation via Supermartingales.” <i>Proceedings of the ACM on Programming Languages</i>. ACM, 2026. <a href=\"https://doi.org/10.1145/3808296\">https://doi.org/10.1145/3808296</a>.","ama":"Chatterjee K, Goharshady E, Zikelic D. SuperDP: Differential privacy refutation via supermartingales. <i>Proceedings of the ACM on Programming Languages</i>. 2026;10(PLDI). doi:<a href=\"https://doi.org/10.1145/3808296\">10.1145/3808296</a>"},"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"related_material":{"record":[{"relation":"research_data","id":"22134","status":"public"}]},"acknowledgement":"The authors would like to thank Petr Novotný for valuable discussions that helped shape this work.\r\nThis research was supported by the Singapore Ministry of Education (MOE) Academic Research\r\nFund (AcRF) Tier 1 grant (Proposal ID: 25-SIS-SMU-009), Vienna Science and Technology Fund\r\n(WWTF), State of Lower Austria [Grant ID 10.47379/ICT25017], ERC CoG 863818 (ForM-SMArt),\r\nand Austrian Science Fund (FWF) 10.55776/COE12.","publication_identifier":{"eissn":["2475-1421"]},"status":"public","publication":"Proceedings of the ACM on Programming Languages","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","OA_type":"gold","date_published":"2026-06-08T00:00:00Z","title":"SuperDP: Differential privacy refutation via supermartingales","article_number":"218","oa_version":"Published Version","ec_funded":1,"quality_controlled":"1","PlanS_conform":"1"},{"publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-091-6"]},"status":"public","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication_status":"published","acknowledged_ssus":[{"_id":"ScienComp"}],"OA_place":"publisher","date_published":"2026-09-08T00:00:00Z","oa_version":"Published Version","title":"Trustworthy machine learning in high dimensions","degree_awarded":"PhD","type":"dissertation","date_created":"2026-09-08T13:40:08Z","day":"08","corr_author":"1","citation":{"ama":"Bombari S. Trustworthy machine learning in high dimensions. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-22857\">10.15479/AT-ISTA-22857</a>","mla":"Bombari, Simone. <i>Trustworthy Machine Learning in High Dimensions</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-22857\">10.15479/AT-ISTA-22857</a>.","chicago":"Bombari, Simone. “Trustworthy Machine Learning in High Dimensions.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-22857\">https://doi.org/10.15479/AT-ISTA-22857</a>.","apa":"Bombari, S. (2026). <i>Trustworthy machine learning in high dimensions</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-22857\">https://doi.org/10.15479/AT-ISTA-22857</a>","short":"S. Bombari, Trustworthy Machine Learning in High Dimensions, Institute of Science and Technology Austria, 2026.","ista":"Bombari S. 2026. Trustworthy machine learning in high dimensions. Institute of Science and Technology Austria.","ieee":"S. Bombari, “Trustworthy machine learning in high dimensions,” Institute of Science and Technology Austria, 2026."},"project":[{"_id":"92099302-16d5-11f0-9cad-f9a785f54fbd","name":"Trustworthy Deep Learning Theory: Private Over-Parameterized Models and Robust LLMs"},{"name":"Inference in High Dimensions: Light-speed Algorithms and Information Limits","_id":"911e6d1f-16d5-11f0-9cad-c5c68c6a1cdf","grant_number":"101161364"},{"name":"Bilateral Artificial Intelligence (Mondelli)","_id":"74caaef7-b034-11f1-8f2d-e0e993bb422e","grant_number":"COE12"}],"related_material":{"record":[{"status":"public","id":"12537","relation":"part_of_dissertation"},{"id":"18972","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"18973"},{"status":"public","relation":"part_of_dissertation","id":"21324"},{"id":"22894","relation":"part_of_dissertation","status":"public"},{"id":"19627","relation":"part_of_dissertation","status":"public"},{"id":"12859","relation":"part_of_dissertation","status":"public"}]},"acknowledgement":"This project was partially supported by the 2019 Lopez-Loreta prize,\r\nthe European Union (ERC, INF2\r\n, project number 101161364), the Austrian Science Fund\r\n(FWF) 10.55776/COE12, and a Google PhD fellowship in machine intelligence. Furthermore,\r\nthe candidate acknowledges the support from the Scientific Service Units of the Institute of\r\nScience and Technology Austria through resources provided by Scientific Computing.","_id":"22857","has_accepted_license":"1","oa":1,"ddc":["519"],"das_tickbox":"0","language":[{"iso":"eng"}],"department":[{"_id":"GradSch"},{"_id":"MaMo"}],"abstract":[{"lang":"eng","text":"Artificial intelligence and machine learning have undergone an unprecedented evolution in the past decade, motivating a research effort toward a theory able to capture the qualitative behavior of large-scale neural systems. A central puzzle has been the clear benefit of scaling architecture size and overfitting the training set in supervised learning tasks. This evidence, in apparent contradiction with classical statistical learning theory, pushed researchers to develop a new theory capturing the interplay between the algorithmic and architectural bias of training and the specific target function, differently from previous methods rooted in uniform stability.\r\nThis approach has enabled a grounded understanding of novel learning regimes, typically through formal limits where the number of training samples $n$, data dimensions $d$, and model parameters $p$ grow to infinity at different rates. \\\\\r\nIn this thesis, we follow this approach, focusing on the trustworthiness of high-dimensional models: properties that are difficult to control during training or deployment and often emerge under unpredictable or adversarial conditions. In such settings, it is crucial to formally ensure a priori the reliability of machine learning systems.\r\nFirst, we study data memorization, both as label fitting and as the storage of private information about training samples in trained parameters. We prove that $p = \\Omega(n)$ parameters are sufficient for a deep neural network to memorize a generic set of labels, and for a model to memorize spurious features across training data. We then give evidence that $p = \\Omega(dn)$ parameters are instead necessary for an adversary to reconstruct the full training set from the trained parameters.\r\nSecond, we study robustness, both to adversarial perturbations and to distribution shift. We first prove that $p = \\Omega(dn)$ parameters can be sufficient for a class of neural networks to overfit the training data while guaranteeing robustness to adversarial perturbations. Then, we focus on spurious correlations learning in high-dimensional regression, studying the effect of the ridge regularization parameter in the proportional regime $n = \\Theta(d)$, and connecting it via an equivalence argument to the role of over-parameterization $p = \\Omega(n)$ in neural networks. We also investigate the architectural bias of attention-based networks, showing that they are sensitive to the replacement of individual words in an embedded sentence, allowing them to generalize on sentences where the contextual meaning depends on one or few words.\r\nFinally, we study differentially private optimization in high-dimensional regimes. We prove that standard private gradient methods do not suffer in the over-parameterized regime $p = \\Omega(n)$, challenging the current wisdom based on stability-derived generalization bounds. We then consider linear regression in the proportional regime $n = \\Theta(d)$, showing that standard private gradient descent can achieve optimal rates under appropriate hyper-parameter scaling, such as sufficiently small gradient clipping constants, whose role is still debated in practice."}],"article_processing_charge":"No","researchdata_availability":"no","doi":"10.15479/AT-ISTA-22857","supervisor":[{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"}],"page":"446","author":[{"last_name":"Bombari","id":"ca726dda-de17-11ea-bc14-f9da834f63aa","first_name":"Simone","full_name":"Bombari, Simone"}],"keyword":["machine learning","high-dimensional statistics","deep learning theory","privacy","memorization","robustness"],"alternative_title":["ISTA Thesis"],"supplementarymaterial":"no","fulldoi":"https://doi.org/10.15479/AT-ISTA-22857","doi_confirm":"1","publisher":"Institute of Science and Technology Austria","year":"2026","month":"09","file_date_updated":"2026-09-10T10:03:48Z","file":[{"date_created":"2026-09-08T13:28:38Z","content_type":"application/zip","creator":"sbombari","file_id":"22859","relation":"source_file","file_name":"Thesis copy.zip","access_level":"closed","date_updated":"2026-09-08T13:28:38Z","file_size":99154325,"checksum":"8eab99d6dc6e4476826bdfc7c00fdebb"},{"success":1,"file_name":"2026_Bombari_Simone_Thesis.pdf","relation":"main_file","content_type":"application/pdf","creator":"sbombari","file_id":"22898","date_created":"2026-09-10T10:03:48Z","checksum":"007033bafe4622ff4c2e758301354df1","file_size":12856211,"date_updated":"2026-09-10T10:03:48Z","access_level":"open_access"}],"date_updated":"2026-09-21T13:07:01Z"}]