71 citations · 437 across the 49 of their papers we have counts for
5 papers · 1 filter
Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
Daniel A. Spielman, Shang-Hua Teng
This paper has been divided into three papers. arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time
Daniel A. Spielman, Shang-Hua Teng
We present a linear-system solver that, given an -by- symmetric positive semi-definite, diagonally dominant matrix with non-zero entries and an -vector $\bb $, pro…
Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
Arvind Sankar, Daniel A. Spielman, Shang-Hua Teng
Let $\orig{A}$ be any matrix and let be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that has large condition number. Using this result, we prov…
Smoothed Analysis of Interior-Point Algorithms: Condition Number
John Dunagan, Daniel A. Spielman, Shang-Hua Teng
We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).
Smoothed Analysis of Interior-Point Algorithms: Termination
Daniel A. Spielman, Shang-Hua Teng
We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by…