2014
Twice-Ramanujan Sparsifiers
Batson J, Spielman D, Srivastava N. Twice-Ramanujan Sparsifiers. SIAM Review 2014, 56: 315-334. DOI: 10.1137/130949117.Peer-Reviewed Original ResearchSpectral sparsifierLaplacian matrixPositive semidefinite matricesNonnegative diagonal matrixNumber of edgesNumber of verticesDeterministic polynomial time algorithmGeneral theoremSemidefinite matricesNonzero entriesPolynomial time algorithmSparse graphsDiagonal matrixQuadratic formSparse approximationSparsifiersWeighted graphReal matricesSpecial caseTime algorithmGraphVerticesMatrixTheoremApproximation
2012
Twice-Ramanujan Sparsifiers
Batson J, Spielman D, Srivastava N. Twice-Ramanujan Sparsifiers. SIAM Journal On Computing 2012, 41: 1704-1721. DOI: 10.1137/090772873.Peer-Reviewed Original Research
2009
Twice-ramanujan sparsifiers
Batson J, Spielman D, Srivastava N. Twice-ramanujan sparsifiers. 2009, 255-262. DOI: 10.1145/1536414.1536451.Peer-Reviewed Original ResearchSpectral sparsifierLinear-sized spectral sparsifiersComplete graphNumber of edgesNumber of verticesDeterministic polynomial time algorithm