49 citations · 263 across the 36 of their papers we have counts for
4 papers · 1 filter
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, John Peebles +4
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of t…
Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, John Peebles +2
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in time (The $\tilde{…
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem
Jan Hązła, Thomas Holenstein, Anup Rao
We study a special kind of bounds (so called forbidden subgraph bounds, cf. Feige, Verbitsky '02) for parallel repetition of multi-prover games. First, we show that forbidden subgr…
Agnostic Estimation of Mean and Covariance
Kevin A. Lai, Anup B. Rao, Santosh Vempala
We consider the problem of estimating the mean and covariance of a distribution from iid samples in , in the presence of an fraction of malicious noise; this is i…