49 citations · 263 across the 36 of their papers we have counts for
14 papers · 1 filter
The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration
Tung Mai, Anup Rao
An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace.…
Dynamic Vector Bin Packing for Online Resource Allocation in the Cloud
Aniket Murhekar, David Arbour, Tung Mai +1
Several cloud-based applications, such as cloud gaming, rent servers to execute jobs which arrive in an online fashion. Each job has a resource demand and must be dispatched to a c…
Optimal Sketching Bounds for Sparse Linear Regression
Tung Mai, Alexander Munteanu, Cameron Musco +3
We study oblivious sketching for -sparse linear regression under various loss functions such as an norm, or from a broad class of hinge-like loss functions, which inclu…
Online Discrepancy Minimization via Persistent Self-Balancing Walks
David Arbour, Drew Dimmery, Tung Mai +1
We study the online discrepancy minimization problem for vectors in in the oblivious setting where an adversary is allowed fix the vectors in…
Approximate Maximum Matching in Random Streams
Alireza Farhadi, MohammadTaghi Hajiaghayi, Tung Mai +2
In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, an algorithm receive…
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
David Durfee, John Peebles, Richard Peng +1
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant o…
Concave Flow on Small Depth Directed Networks
Tung Mai, Richard Peng, Anup B. Rao +1
Small depth networks arise in a variety of network related applications, often in the form of maximum flow and maximum weighted matching. Recent works have generalized such methods…
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{…
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…
Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
Peter Chin, Anup Rao, Van Vu
In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with blocks, for any fixed. Our algorithm works with graphs havi…
Preconditioning in Expectation
Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki +2
We show that preconditioners constructed by random sampling can perform well without meeting the standard requirements of iterative methods. When applied to graph Laplacians, this…