12 citations · 12 across the 3 of their papers we have counts for
4 papers
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne +2
In this paper, we introduce a new, spectral notion of approximation between directed graphs, which we call singular value (SV) approximation. SV-approximation is stronger than prev…
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…
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi +1
In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. e…
From Duels to Battefields: Computing Equilibria of Blotto and Other Games
AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi +3
We study the problem of computing Nash equilibria of zero-sum games. Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in…