16 citations · 17 across the 15 of their papers we have counts for
18 papers
Finding Nearly-Periodic Components in Digraphs and Markov Chains from the Spectrum of Rotated Laplacian Matrices
Salil Vadhan, Jiyu Zhang
Inspired by recent advances in notions of spectral approximation of digraphs [Ahm+20], we study spectral algorithms for finding periodic structures in digraphs via the spectrum of…
Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
Sara Fish, Yannai A. Gonczarowski, Jason Z. Tang +1
The differentially private (DP) facility location problem seeks to determine a socially optimal placement for a public facility while ensuring that each participating agent's locat…
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties
Aaron Putterman, Salil Vadhan, Vadim Zaripov
Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique o…
Practitioners' Perspectives on a Differential Privacy Deployment Registry
Priyanka Nanayakkara, Elena Ghazi, Salil Vadhan
Differential privacy (DP) -- a principled approach to producing statistical data products with strong, mathematically provable privacy guarantees for the individuals in the underly…
Singular Values Versus Expansion in Directed and Undirected Graphs
Jake Ruotolo, Salil Vadhan
We relate the nontrivial singular values of the normalized adjacency matrix of an Eulerian directed graph to combinatorial measures of graph expansion: \\ 1. We in…
Generalized and Unified Equivalences between Hardness and Pseudoentropy
Lunjia Hu, Salil Vadhan
Pseudoentropy characterizations give quantitatively precise formulations of the relationship between computational hardness and computational randomness. We prove a unified pseudoe…
Securing Unbounded Differential Privacy Against Timing Attacks
Zachary Ratliff, Salil Vadhan
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 th…
Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
Tommaso d'Orsi, Chris Jones, Jake Ruotolo +2
Whether or not the Sparsest Cut problem admits an efficient -approximation algorithm is a fundamental algorithmic question with connections to geometry and the Unique Games C…
Characterizing the Distinguishability of Product Distributions through Multicalibration
Cassandra Marcussen, Aaron Putterman, Salil Vadhan
Given a sequence of samples promised to be drawn from one of two distributions , a well-studied problem in statistics is to decide dis…
Concurrent Composition for Differentially Private Continual Mechanisms
Monika Henzinger, Roodabeh Safavi, Salil Vadhan
Many intended uses of differential privacy involve a that is set up to run continuously over a long period of time, making more statistical releases…
"I inherently just trust that it works": Investigating Mental Models of Open-Source Libraries for Differential Privacy
Patrick Song, Jayshree Sarathy, Michael Shoemate +1
Differential privacy (DP) is a promising framework for privacy-preserving data science, but recent studies have exposed challenges in bringing this theoretical framework for privac…
A Framework for Differential Privacy Against Timing Attacks
Zachary Ratliff, Salil Vadhan
The standard definition of differential privacy (DP) ensures that a mechanism's output distribution on adjacent datasets is indistinguishable. However, real-world implementations o…
Programming Frameworks for Differential Privacy
Marco Gaboardi, Michael Hay, Salil Vadhan
Many programming frameworks have been introduced to support the development of differentially private software applications. In this chapter, we survey some of the conceptual ideas…
Membership Inference Attacks and Privacy in Topic Modeling
Nico Manzonelli, Wanrong Zhang, Salil Vadhan
Recent research shows that large language models are susceptible to privacy attacks that infer aspects of the training data. However, it is unclear if simpler generative models, li…
Complexity-Theoretic Implications of Multicalibration
Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan
We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors ar…
Black-Box Training Data Identification in GANs via Detector Networks
Lukman Olagoke, Salil Vadhan, Seth Neel
Since their inception Generative Adversarial Networks (GANs) have been popular generative models across images, audio, video, and tabular data. In this paper we study whether given…
Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters
Samuel Haney, Michael Shoemate, Grace Tian +4
In this paper, we study the concurrent composition of interactive mechanisms with adaptively chosen privacy-loss parameters. In this setting, the adversary can interleave queries t…
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Thomas Steinke, Salil Vadhan, Andrew Wan
We present an explicit pseudorandom generator for oblivious, read-once, width- branching programs, which can read their input bits in any order. The generator has seed length $\…