40 citations · 222 across the 36 of their papers we have counts for
11 papers · 1 filter
On the works of Avi Wigderson
Boaz Barak, Yael Kalai, Ran Raz +2
This is an overview of some of the works of Avi Wigderson, 2021 Abel prize laureate. Wigderson's contributions span many fields of computer science and mathematics. In this survey…
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size
Edward Pyne, Salil Vadhan
Consider the following computational problem: given a regular digraph , two vertices , and a walk length , estimate the probability that a rand…
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 $…
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…
The Complexity of Computing the Optimal Composition of Differential Privacy
Jack Murtagh, Salil Vadhan
In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC'06)) bound the degradation of privacy when c…