40 citations · 222 across the 36 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.CC2019
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…
cs.CC2019
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 $…
cs.CR2019★ 5 cited
Unifying computational entropies via Kullback-Leibler divergence
Rohit Agrawal, Yi-Hsiu Chen, Thibaut Horel +1
We introduce hardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies bo…