2016
Graphs, Vectors, and Matrices
Spielman D. Graphs, Vectors, and Matrices. Bulletin Of The American Mathematical Society 2016, 54: 45-61. DOI: 10.1090/bull/1557.Peer-Reviewed Original Research
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
2013
Spectral sparsification of graphs
Batson J, Spielman D, Srivastava N, Teng S. Spectral sparsification of graphs. Communications Of The ACM 2013, 56: 87-94. DOI: 10.1145/2492007.2492029.Peer-Reviewed Original ResearchSpectral sparsificationApproximate maximum flowLinear systemsSpectral approximationLinear time algorithmCombinatorial optimizationGraph sparsificationLinear equationsDominant matricesArbitrary graphsSparse graphsFast solutionUndirected networksFast algorithmDevelopment of algorithmsSparsificationMinimum cutMaximum flowGraphApproximationAlgorithmEquationsOptimizationImportant toolSolutionA Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
Spielman D, Teng S. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal On Computing 2013, 42: 1-26. DOI: 10.1137/080744888.Peer-Reviewed Original ResearchLinear time algorithmMassive graphsTime algorithmLinear system solverRunning timeSubset of verticesLinear systemsSpectral sparsifierLaplacian matrixNumber edgesSparsest cutSystem solverCorresponding eigenvectorsLocal clustering algorithmSmallest eigenvalueDominant matricesClustering algorithmPartitioning algorithmGraph partitioningWhole graphGraph algorithmsLocal algorithmGraphVerticesBetter clusters
2012
Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations
Spielman D. Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations. Lecture Notes In Computer Science 2012, 7392: 24-26. DOI: 10.1007/978-3-642-31585-5_5.Peer-Reviewed Original ResearchTwice-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
2011
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Christiano P, Kelner J, Madry A, Spielman D, Teng S. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. 2011, 273-282. DOI: 10.1145/1993636.1993674.Peer-Reviewed Original Research
2009
Fitting a graph to vector data
Daitch S, Kelner J, Spielman D. Fitting a graph to vector data. 2009, 201-208. DOI: 10.1145/1553374.1553400.Peer-Reviewed Original Research
2008
Graph sparsification by effective resistances
Spielman D, Srivastava N. Graph sparsification by effective resistances. 2008, 563-568. DOI: 10.1145/1374376.1374456.Peer-Reviewed Original Research
2007
Spectral Graph Theory and its Applications
Spielman D. Spectral Graph Theory and its Applications. 2007, 29-38. DOI: 10.1109/focs.2007.56.Peer-Reviewed Original ResearchSpectral partitioning works: Planar graphs and finite element meshes
Spielman D, Teng S. Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra And Its Applications 2007, 421: 284-305. DOI: 10.1016/j.laa.2006.07.020.Peer-Reviewed Original ResearchBounded-degree planar graphsPlanar graphsSpectral partitioning methodLaplacian matrixSmallest eigenvalueFinite element meshRatio of verticesClass of graphsDimensional meshesElement meshSpectral partitioning techniquesNumerical algorithmFiedler vectorPartitioning methodSmall separatorsTwo-dimensional meshEdge cutGraphSpectral bisectionEigenvaluesPartitioning techniquesMeshBoundsEigenvectorsMatrix
2005
A Lower Bound on Convergence of a Distributed Network Consensus Algorithm
Cao M, Spielman D, Morse A. A Lower Bound on Convergence of a Distributed Network Consensus Algorithm. 2005, 2356-2361. DOI: 10.1109/cdc.2005.1582514.Peer-Reviewed Original Research
2003
Exponential algorithmic speedup by a quantum walk
Childs A, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman D. Exponential algorithmic speedup by a quantum walk. 2003, 59-68. DOI: 10.1145/780542.780552.Peer-Reviewed Original ResearchQuantum algorithmsQuantum walkBlack-box settingGraph traversal problemTime quantum walkQuantum Fourier transformPrevious quantum algorithmsClassical computersQuantum computerTraversal problemContinuous-time quantum walkClassical algorithmsBox settingSubexponential timeAlgorithmic speedupQuantumAlgorithmComputerSpeedupDifferent techniquesGraphFourier transform
2001
Introduction to the Special Issue on Codes on Graphs and Iterative Algorithms
Frey B, Koetter R, Forney G, Kschischang F, Mceliece R, Spielman D. Introduction to the Special Issue on Codes on Graphs and Iterative Algorithms. IEEE Transactions On Information Theory 2001, 47: 493. DOI: 10.1109/tit.2001.910571.Peer-Reviewed Original ResearchEfficient Erasure Correcting Codes
Luby M, Mitzenmacher M, Shokrollahi M, Spielman D. Efficient Erasure Correcting Codes. IEEE Transactions On Information Theory 2001, 47: 569. DOI: 10.1109/18.910575.Peer-Reviewed Original Research
1996
Expander codes
Sipser M, Spielman D. Expander codes. IEEE Transactions On Information Theory 1996, 42: 1710-1722. DOI: 10.1109/18.556667.Peer-Reviewed Original ResearchSpectral partitioning works: planar graphs and finite element meshes
Spielman D, Teng S. Spectral partitioning works: planar graphs and finite element meshes. 2011 IEEE 52nd Annual Symposium On Foundations Of Computer Science 1996, 96-105. DOI: 10.1109/sfcs.1996.548468.Peer-Reviewed Original ResearchBounded-degree planar graphsPlanar graphsSpectral partitioning methodLaplacian matrixSmallest eigenvalueFinite element meshRatio of verticesClass of graphsDimensional meshesElement meshSpectral partitioning techniquesNumerical algorithmFiedler vectorPartitioning methodSmall separatorsTwo-dimensional meshEdge cutGraphSpectral bisectionEigenvaluesPartitioning techniquesMeshEigenvectorsBoundsMatrix
1994
Expander codes
Sipser M, Spielman D. Expander codes. 1994, 566-576. DOI: 10.1109/sfcs.1994.365734.Peer-Reviewed Original Research