7 citations · 7 across the 2 of their papers we have counts for
4 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…
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…
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…