4 papers
Numerical Linear Algebra in Linear Space
Yiping Liu, Hoai-An Nguyen, Junzhao Yang
We present a randomized linear-space solver for general linear systems with and $\mathbf{b} \in \mathb…
Relative Error Fair Clustering in the Weak-Strong Oracle Model
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H. -C. Jiang +4
We study fair clustering problems in a setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak or…
Entrywise Approximation for Matrix Inversion and Linear Systems
Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang
We study the bit complexity of inverting diagonally dominant matrices, which are associated with random walk quantities such as hitting times and escape probabilities. Such quantit…
Entrywise Approximate Laplacian Solving
Jingbang Chen, Mehrdad Ghadiri, Hoai-An Nguyen +2
We study the escape probability problem in random walks over graphs. Given vertices, and , the problem asks for the probability that a random walk starting at will hi…