HOME / PUBLICATIONS /

Publications by Year: 2022

2022
Alabi, Daniel, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. “Differentially private simple linear regression.” Proceedings on 23rd Privacy Enhancing Technologies Symposium (PoPETS ‘22), 2022, 2022 (2), 184–204. Publisher's VersionAbstract

Version History: Preliminary version posted as arXiv:2007.05157 [cs.LG] and presented as a poster at TPDP ‘20.

Abstract: Forthcoming.

PoPETS 2022.pdf
Casacuberta, Sílvia, Michael Shoemate, Salil Vadhan, and Connor Wagaman. “Widespread underestimation of sensitivity in differentially private libraries and how to fix it.” Proceedings of the 29th ACM SIGSAC Conference on Computer and Communications Security (CCS '22), 2022. Publisher's VersionAbstract
Version History: Preprint version posted as arXiv:2207.10635 [cs.CR].
ArXiv 2022.pdf CCS 2022.pdf
Lee, Chin Ho, Edward Pyne, and Salil Vadhan. “Fourier growth of regular branching programs.” Proceedings of the International Conference on Randomization and Computation (RANDOM '22). Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022. Publisher's VersionAbstract

Version History: Preliminary version posted as https://eccc.weizmann.ac.il/report/2022/034/.

Abstract: Forthcoming.

RANDOM 22.pdf
Pyne, Edward, and Salil Vadhan. “Deterministic approximation of random walks via queries in graphs of unbounded size.” Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA '22), 2022, 57-67. Publisher's VersionAbstract

Version History: Preliminary version posted as arXiv:2111.01997 [cs.CC].

Abstract: Forthcoming.

SOSA 22.pdf
Gong, Roubin, Erica L. Groshen, and Salil Vadhan, ed. “Special Issue on Differential Privacy for the 2020 U.S. Census: Can we Make Data Both Private and Useful?” Harvard Data Science Review , 2022, Special Issue, 2. Publisher's VersionAbstract
Note: Prof. Vadhan is also the author of the editor's foreword to this issue.
Golowich, Louis, and Salil Vadhan. “Pseudorandomness of expander random walks for symmetric functions and permutation branching programs.” Proceedings of the 37th Computational Complexity Conference (CCC '22) . Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022. Publisher's VersionAbstract

Version History: Full version (25 June 2022): https://eccc.weizmann.ac.il/report/2022/024/

Abstract: We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. A line of prior work has shown that random walks on expanders with second largest eigenvalue λ fool symmetric functions up to a O(λ) error in total variation distance, but only for the case where the vertices are labeled with symbols from a binary alphabet, and with a suboptimal dependence on the bias of the labeling. We generalize these results to labelings with an arbitrary alphabet, and for the case of binary labelings we achieve an optimal dependence on the labeling bias. We extend our analysis to unify it with and strengthen the expander-walk Chernoff bound. We then show that expander walks fool permutation branching programs up to a O(λ) error in ℓ2-distance, and we prove that much stronger bounds hold for programs with a certain structure. We also prove lower bounds to show that our results are tight. To prove our results for symmetric functions, we analyze the Fourier coefficients of the relevant distributions using linear-algebraic techniques. Our analysis for permutation branching programs is likewise linear-algebraic in nature, but also makes use of the recently introduced singular-value approximation notion for matrices (Ahmadinejad et al. 2021).

CCC 2022.pdf