16 citations · 29 across the 6 of their papers we have counts for
8 papers
Spectral Sparsification via Bounded-Independence Sampling
Dean Doron, Jack Murtagh, Salil Vadhan +1
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph on vertices described…
High-precision Estimation of Random Walks in Small Space
AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh +3
We provide a deterministic -space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within…
Deterministic Approximation of Random Walks in Small Space
Jack Murtagh, Omer Reingold, Aaron Sidford +1
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph , a positive integer , and a set of vertices, approximates the conductance of $…
Thwarting Adversarial Examples: An -RobustSparse Fourier Transform
Mitali Bafna, Jack Murtagh, Nikhil Vyas
We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worst-case noise, namely a bounded numbe…
Usable Differential Privacy: A Case Study with PSI
Jack Murtagh, Kathryn Taylor, George Kellaris +1
Differential privacy is a promising framework for addressing the privacy concerns in sharing sensitive datasets for others to analyze. However differential privacy is a highly tech…
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Jack Murtagh, Omer Reingold, Aaron Sidford +1
We give a deterministic -space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating h…