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