16 citations · 17 across the 15 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…