# Publications Sort & Filters close ## Filters Publication Taxonomies expand\_more - Complexity of Counting (3) - Computational Complexity (63) - Cryptography (38) - Game Theory (6) - Law, Policy, Ethics, STS (7) - Privacy (35) - Proof Systems (20) - Pseudorandomness (44) - Software, Systems, HCI, Security (1) - Spectral Graph Theory (2) - Statistics & ML (15) - Surveys (8) Publication Grants expand\_more - Census CB16ADR016001 (4) - Census CB20ADR0160001 (3) - Google Gift 2011 (8) - Guggenheim Fellowship (7) - Miller Institute (1) - NSF BCS-2218803 (2) - NSF CCF-0133096 (17) - NSF CCF-1116616 (10) - NSF CCF-1420938 (2) - NSF CCF-1749750 (1) - NSF CCF-1763299 (11) - NSF CNS-0205423 (3) - NSF CNS-0430336 (11) - NSF CNS-0831289 (16) - NSF CNS-1237235 (19) - NSF CNS-1565387 (2) - NSF TI-2303681 (1) - ONR N00014-04-1-0478 (18) - Simons Investigator (40) - Sloan Fellowship (12) - Sloan Foundation 2015 (9) - Sloan OpenDP (1) - US-Israel BSF 2002246 (18) - US-Israel BSF 2010196 (5) Year of Publication expand\_more 2026 (1) 2025 (11) 2024 (10) 2023 (11) 2022 (6) 2021 (6) 2020 (8) 2019 (3) 2018 (7) 2017 (8) 2016 (8) 2015 (4) 2014 (3) 2013 (7) 2012 (7) 2011 (4) 2010 (6) 2009 (9) 2008 (6) 2007 (3) 2006 (8) 2005 (3) 2003 (1) 2002 (1) 2001 (1) 1999 (2) 1998 (1) Search Within Results Search Within Results search ## 145 results Show filters filter\_alt Sort by Year of PublicationAlphabetical A-Z sort ## 145 results Download 145 citations download- [BibTeX](/node/779041/export?format=bibtex) - [EndNote X3 XML](/node/779041/export?format=endnote8) - [EndNote 7 XML](/node/779041/export?format=endnote7) - [Endnote tagged](/node/779041/export?format=tagged) - [Marc](/node/779041/export?format=marc) - [PubMedId](/node/779041/export?format=pubmed_id) - [RIS](/node/779041/export?format=ris) ### 2026 Putterman, Aaron, Salil Vadhan, and Vadim Zaripov. “[Bounded Independence Edge Sampling for Combinatorial Graph Properties](/publication/bounded-independence-edge-sampling-combinatorial-graph-properties).” Putterman, Aaron, Salil Vadhan, and Vadim Zaripov. “[Bounded Independence Edge Sampling for Combinatorial Graph Properties](/publication/bounded-independence-edge-sampling-combinatorial-graph-properties).” - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfPuttermanVaZa2026.pdf](/sites/g/files/omnuum4266/files/2026-04/PuttermanVaZa2026.pdf) - [ArXiv Version](https://arxiv.org/abs/2603.25095) **Version History:** Thu 26 Mar: [arXiv 2603.25095 \[cs.DS\]](https://arxiv.org/abs/2603.25095) **Abstract:** Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads... - [ picture\_as\_pdfPuttermanVaZa2026.pdf](/sites/g/files/omnuum4266/files/2026-04/PuttermanVaZa2026.pdf) - [ArXiv Version](https://arxiv.org/abs/2603.25095) ### 2025 Ratliff, Zachary, and Salil Vadhan. “[Securing Unbounded Differential Privacy Against Timing Attacks](/publication/securing-unbounded-differential-privacy-against-timing-attacks-0)”. In *Theory of Cryptography Conference (TCC 2025)*. 2025. Reprint, Aarhus, Denmark: In: Applebaum, Benny, and Huijia (Rachel) Lin, eds., Proceedings of the 23rd Theory of Cryptography Conference (TCC ’25) vol. 16251 of Lecture Notes in Computer Science, pages 378–414. IACR, Springer, December 2025, 2025. Ratliff, Zachary, and Salil Vadhan. “[Securing Unbounded Differential Privacy Against Timing Attacks](/publication/securing-unbounded-differential-privacy-against-timing-attacks-0)”. In *Theory of Cryptography Conference (TCC 2025)*. 2025. Reprint, Aarhus, Denmark: In: Applebaum, Benny, and Huijia (Rachel) Lin, eds., Proceedings of the 23rd Theory of Cryptography Conference (TCC ’25) vol. 16251 of Lecture Notes in Computer Science, pages 378–414. IACR, Springer, December 2025, 2025. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfRatliffVa2025 ArXiv.pdf](/sites/g/files/omnuum4266/files/2026-04/RatliffVa2025%20ArXiv.pdf) - [Publisher's Version](https://dl.acm.org/doi/10.1007/978-3-032-12290-2_13) **Version History:** Full version posted as [arXiv:2506.07868 \[cs.CR\]](https://arxiv.org/abs/2506.07868). **Abstract:** Recent works have started to theoretically investigate how we can protect differentially private programs against timing attacks, by making the joint distribution the output and... - [ picture\_as\_pdfRatliffVa2025 ArXiv.pdf](/sites/g/files/omnuum4266/files/2026-04/RatliffVa2025%20ArXiv.pdf) - [Publisher's Version](https://dl.acm.org/doi/10.1007/978-3-032-12290-2_13) Nanayakkara, Priyanka, Elena Ghazi, and Salil Vadhan. “[Practitioners’ Perspectives on a Differential Privacy Deployment Registry](/publication/practitioners-perspectives-differential-privacy-deployment-registry).” Nanayakkara, Priyanka, Elena Ghazi, and Salil Vadhan. “[Practitioners’ Perspectives on a Differential Privacy Deployment Registry](/publication/practitioners-perspectives-differential-privacy-deployment-registry).” - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfNanayakkaraGhVa 2025.pdf](/sites/g/files/omnuum4266/files/2026-04/NanayakkaraGhVa%202025.pdf) - [ArXiv Version](https://arxiv.org/abs/2509.13509) Differential privacy (DP)—a principled approach to producing statistical data products (e.g., summary statistics, machine learning models) with strong, mathematically provable privacy guarantees for the individuals in the underlying dataset—has seen... - [ picture\_as\_pdfNanayakkaraGhVa 2025.pdf](/sites/g/files/omnuum4266/files/2026-04/NanayakkaraGhVa%202025.pdf) - [ArXiv Version](https://arxiv.org/abs/2509.13509) Ruotolo, Jake, and Salil Vadhan. “[Singular Values versus Expansion in Directed and Undirected Graphs](/publication/singular-values-versus-expansion-directed-and-undirected-graphs).” Ruotolo, Jake, and Salil Vadhan. “[Singular Values versus Expansion in Directed and Undirected Graphs](/publication/singular-values-versus-expansion-directed-and-undirected-graphs).” - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfRuotoloVa 2025.pdf](/sites/g/files/omnuum4266/files/2026-04/RuotoloVa%202025.pdf) - [ArXiv Version](https://arxiv.org/abs/2508.17539) We relate the nontrivial singular values σ2,…,σn of the normalized adjacency matrix of an Eulerian directed graph to combinatorial measures of graph expansion: \\\\ 1. We introduce a new directed analogue of conductance ϕdir, and prove a Cheeger-like... - [ picture\_as\_pdfRuotoloVa 2025.pdf](/sites/g/files/omnuum4266/files/2026-04/RuotoloVa%202025.pdf) - [ArXiv Version](https://arxiv.org/abs/2508.17539) Canonne, Clément L., Francis E. Su, and Salil P. Vadhan. “[The Randomness Complexity of Differential Privacy](/publication/randomness-complexity-differential-privacy)”. In *16th Innovations in Theoretical Computer Science Conference (ITCS 2025)*. Columbia University, New York, New York, United States: Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.27. Canonne, Clément L., Francis E. Su, and Salil P. Vadhan. “[The Randomness Complexity of Differential Privacy](/publication/randomness-complexity-differential-privacy)”. In *16th Innovations in Theoretical Computer Science Conference (ITCS 2025)*. Columbia University, New York, New York, United States: Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.27. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ descriptionPublisher's Version](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.27) - [ picture\_as\_pdfITCS 2025.pdf](/sites/g/files/omnuum4266/files/2025-03/ITCS%202025.pdf) - [ picture\_as\_pdfECCC 2024.pdf](/sites/g/files/omnuum4266/files/2025-01/ECCC%202024.pdf) **Version History:** earlier version published in ECCC in November 2024: We initiate the study of the randomness complexity of differential privacy, i.e., how many random bits an algorithm needs in order to... - [ descriptionPublisher's Version](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.27) - [ picture\_as\_pdfITCS 2025.pdf](/sites/g/files/omnuum4266/files/2025-03/ITCS%202025.pdf) - [ picture\_as\_pdfECCC 2024.pdf](/sites/g/files/omnuum4266/files/2025-01/ECCC%202024.pdf) Clementi, Andrea, Venkatesan Guruswami, Kristin Kane, Alon Rosen, Nikhil Srivastava, Salil Vadhan, and Riccardo Zecchina. “[Obituary for Luca Trevisan](/publication/obituary-luca-trevisan)”. *Bulletin of European Association for Theoretical Computer Science*, 2025. Clementi, Andrea, Venkatesan Guruswami, Kristin Kane, Alon Rosen, Nikhil Srivastava, Salil Vadhan, and Riccardo Zecchina. “[Obituary for Luca Trevisan](/publication/obituary-luca-trevisan)”. *Bulletin of European Association for Theoretical Computer Science*, 2025. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfClGuKaRoSrVaZe25-EATCS.pd...](/sites/g/files/omnuum4266/files/2025-06/ClGuKaRoSrVaZe25-EATCS.pdf) - [Publisher's Version](http://bulletin.eatcs.org/index.php/beatcs/article/view/830) The Theoretical Computer Science Community is heartbroken by the untimely loss of Luca Trevisan, who passed away on June 19, 2024 in Milan at the age of 52. His husband, Junce Zhang, was at his side along with a few other dear friends and colleagues. Luca... - [ picture\_as\_pdfClGuKaRoSrVaZe25-EATCS.pd...](/sites/g/files/omnuum4266/files/2025-06/ClGuKaRoSrVaZe25-EATCS.pdf) - [Publisher's Version](http://bulletin.eatcs.org/index.php/beatcs/article/view/830) Gaboardi, Marco, Michael Hay, and Salil Vadhan. “[Programming Frameworks for Differential Privacy](/publication/programming-frameworks-differential-privacy)”. In *Differential Privacy in Artificial Intelligence: From Theory to Practice*, edited by Ferdinando Fioretto and Pascal Van Hentenryck, 407-39. Boston, Massachusetts: NOW Publishers, 2025. Gaboardi, Marco, Michael Hay, and Salil Vadhan. “[Programming Frameworks for Differential Privacy](/publication/programming-frameworks-differential-privacy)”. In *Differential Privacy in Artificial Intelligence: From Theory to Practice*, edited by Ferdinando Fioretto and Pascal Van Hentenryck, 407-39. Boston, Massachusetts: NOW Publishers, 2025. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfGaboardiHaVa2024.pdf](/sites/g/files/omnuum4266/files/2025-11/GaboardiHaVa2024.pdf) - [ picture\_as\_pdfGaboardiHaVa2025 – NOW ...](/sites/g/files/omnuum4266/files/2025-11/GaboardiHaVa2025%20%E2%80%93%20NOW%20Publishers.pdf) - [Publisher's Version](https://www.nowpublishers.com/Article/BookDetails/9781638284765) **Version History:** originally published on ArXiv: . Many programming frameworks have been introduced to support the development of differentially private software applications. In this chapter, we survey some of the... - [ picture\_as\_pdfGaboardiHaVa2024.pdf](/sites/g/files/omnuum4266/files/2025-11/GaboardiHaVa2024.pdf) - [ picture\_as\_pdfGaboardiHaVa2025 – NOW ...](/sites/g/files/omnuum4266/files/2025-11/GaboardiHaVa2025%20%E2%80%93%20NOW%20Publishers.pdf) - [Publisher's Version](https://www.nowpublishers.com/Article/BookDetails/9781638284765) Marcussen, Cassandra, Aaron Putterman, and Salil P. Vadhan. “[Characterizing the Distinguishability of Product Distributions through Multicalibration](/publication/characterizing-distinguishability-product-distributions-through-multicalibration-0)”. In *40th Computational Complexity Conference (CCC ’25)*. Toronto, Canada: Srikanth Srinivasan, ed., Proceedings of the 40th Computational Complexity Conference (CCC ’25), vol. 330 of LIPIcs, pages 19:1-19:19. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.CCC.2025.19. Marcussen, Cassandra, Aaron Putterman, and Salil P. Vadhan. “[Characterizing the Distinguishability of Product Distributions through Multicalibration](/publication/characterizing-distinguishability-product-distributions-through-multicalibration-0)”. In *40th Computational Complexity Conference (CCC ’25)*. Toronto, Canada: Srikanth Srinivasan, ed., Proceedings of the 40th Computational Complexity Conference (CCC ’25), vol. 330 of LIPIcs, pages 19:1-19:19. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.CCC.2025.19. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfMarcussenPuVa2025.pdf](/sites/g/files/omnuum4266/files/2026-04/MarcussenPuVa2025.pdf) - [Publisher's Version](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.19) **Version History:** - Full version posted as [arXiv:2412.03562 \[cs.CR\]](https://arxiv.org/abs/2412.03562). - Earlier ArXiv versions include [February 2024 (v1);](https://arxiv.org/abs/2412.03562) [February 2025 (v2);](https://arxiv.org/abs/2412.03562v2) [March 2025 (v3)](https://arxiv.org/abs/2412.03562v3), and [July 2025 (v4)](https://arxiv.org/abs/2412.03562v4). **Abstract:** Given a sequence of samples *x*1,...,*xk* promised to be drawn from one of... - [ picture\_as\_pdfMarcussenPuVa2025.pdf](/sites/g/files/omnuum4266/files/2026-04/MarcussenPuVa2025.pdf) - [Publisher's Version](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.19) D’Orsi, Tommaso, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang. “[Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs](/publication/sparsest-cut-and-eigenvalue-multiplicities-low-degree-abelian-cayley-graphs-1)”. In *28th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’25)*. in volume 353 of Leibniz International Proceedings in Informatics (LIPIcs) pages 16:1-16:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Alina Ene and Eshan Chattopadhyay, eds., Proceedings of the 28th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’25), 2025. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2025.16. D’Orsi, Tommaso, Chris Jones, Jake Ruotolo, Salil Vadhan, and Jiyu Zhang. “[Sparsest Cut and Eigenvalue Multiplicities on Low Degree Abelian Cayley Graphs](/publication/sparsest-cut-and-eigenvalue-multiplicities-low-degree-abelian-cayley-graphs-1)”. In *28th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’25)*. in volume 353 of Leibniz International Proceedings in Informatics (LIPIcs) pages 16:1-16:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl-Leibniz-Zentrum für Informatik: Alina Ene and Eshan Chattopadhyay, eds., Proceedings of the 28th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX ’25), 2025. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2025.16. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfd'OrsiJoRuVaZh2025.pdf](/sites/g/files/omnuum4266/files/2026-04/d%27OrsiJoRuVaZh2025.pdf) - [Publisher's Version](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.16) **Version History:** Preliminary version posted as arXiv:2412.17115 \[cs.DS\] **Abstract:** Whether or not the Sparsest Cut problem admits an efficient O(1)-approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique... - [ picture\_as\_pdfd'OrsiJoRuVaZh2025.pdf](/sites/g/files/omnuum4266/files/2026-04/d%27OrsiJoRuVaZh2025.pdf) - [Publisher's Version](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.16) Sarathy, Jayshree, and Salil P. Vadhan. “[Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression](/publication/analyzing-differentially-private-theil-sen-estimator-simple-linear-regression)”. In *25th Privacy Enhancing Technologies Symposium (PoPETS ’25)* . Washington, D.C.: Proceedings of the 25th Privacy Enhancing Technology Symposium (PoPETS ’25), volume 1, pages 216-235, 2025. Sarathy, Jayshree, and Salil P. Vadhan. “[Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression](/publication/analyzing-differentially-private-theil-sen-estimator-simple-linear-regression)”. In *25th Privacy Enhancing Technologies Symposium (PoPETS ’25)* . Washington, D.C.: Proceedings of the 25th Privacy Enhancing Technology Symposium (PoPETS ’25), volume 1, pages 216-235, 2025. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ descriptionPublisher's Version](https://petsymposium.org/popets/2025/popets-2025-0013.pdf) - [ picture\_as\_pdfSarathyVa2025.pdf](/sites/g/files/omnuum4266/files/2026-04/SarathyVa2025.pdf) **Version History:** Preliminary version presented as a poster at the 7th Workshop on the Theory and Practice of Differential Privacy (TPDP '21, July 2021) and posted as [arXiv:2207.13289 \[cs.CR\]](https://arxiv.org/abs/2207.13289) **Abstract:** In this paper, we study differentially private point... - [ descriptionPublisher's Version](https://petsymposium.org/popets/2025/popets-2025-0013.pdf) - [ picture\_as\_pdfSarathyVa2025.pdf](/sites/g/files/omnuum4266/files/2026-04/SarathyVa2025.pdf) Canonne, Clément L., Francis E. Su, and Salil P. Vadhan. “[The Randomness Complexity of Differential Privacy](/publication/randomness-complexity-differential-privacy-0)”. *Leibniz International Proceedings in Informatics (LIPIcs)* 325, no. Raghu Meka, editor, Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) (2025): 20. Canonne, Clément L., Francis E. Su, and Salil P. Vadhan. “[The Randomness Complexity of Differential Privacy](/publication/randomness-complexity-differential-privacy-0)”. *Leibniz International Proceedings in Informatics (LIPIcs)* 325, no. Raghu Meka, editor, Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) (2025): 20. “[Generalized and Unified Equivalences Between Hardness and Pseudoentropy](/publication/generalized-and-unified-equivalences-between-hardness-and-pseudoentropy-0)”. *Lecture Notes in Computer Science* 16271, no. Benny Appelbaum and Huijia (Rachel) Lin, eds., Proceedings of the 23rd Annual Theory of Cryptography Conference (TCC ’25) (2025): 30. “[Generalized and Unified Equivalences Between Hardness and Pseudoentropy](/publication/generalized-and-unified-equivalences-between-hardness-and-pseudoentropy-0)”. *Lecture Notes in Computer Science* 16271, no. Benny Appelbaum and Huijia (Rachel) Lin, eds., Proceedings of the 23rd Annual Theory of Cryptography Conference (TCC ’25) (2025): 30. - add\_circle\_outline do\_not\_disturb\_on Abstract - [ picture\_as\_pdfHuVa 2025 ArXiv.pdf](/sites/g/files/omnuum4266/files/2026-04/HuVa%202025%20ArXiv.pdf) - [Publisher's Version](https://link.springer.com/chapter/10.1007/978-3-032-12290-2_9) **Version History:** - Preliminary version posted as [arXiv:2507.05972 \[cs.CC\]](https://arxiv.org/abs/2507.05972) - Notes: Outstanding Paper Award, TCC 2025. **Abstract:** Pseudoentropy characterizations provide a quantitatively precise demonstration of the close relationship between computational... - [ picture\_as\_pdfHuVa 2025 ArXiv.pdf](/sites/g/files/omnuum4266/files/2026-04/HuVa%202025%20ArXiv.pdf) - [Publisher's Version](https://link.springer.com/chapter/10.1007/978-3-032-12290-2_9) - Previous page chevron\_left - [1](?page=0 "Current page") - [2](?page=1 "Go to page 2") - [3](?page=2 "Go to page 3") - [ Last page 13 ](?page=12 "Go to last page") - [ Next page chevron\_right ](?page=1 "Go to next page")