12 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…
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties
Aaron Putterman, Salil Vadhan, Vadim Zaripov
The paper investigates how bounded‑independence edge sampling can preserve graph properties such as connectivity and cycle‑freeness, and provides explicit derandomization technique…
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…
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…
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…
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…