2024
Balancing Covariates in Randomized Experiments with the Gram–Schmidt Walk Design
Harshaw C, Sävje F, Spielman D, Zhang P. Balancing Covariates in Randomized Experiments with the Gram–Schmidt Walk Design. Journal Of The American Statistical Association 2024, ahead-of-print: 1-13. DOI: 10.1080/01621459.2023.2285474.Peer-Reviewed Original ResearchConservative variance estimatorsLinear functionAverage treatment effectAsymptotic normalityFinite samplesVariance estimationCovariate balanceSupplementary materialsMean square errorRidge regressionLoss functionCovariatesRandomized experimentEstimationPotential outcomesGram-SchmidtLevel of robustnessRobust parameterWalking designConfidence intervalsFunctionSquare errorTreatment effectsRobustnessFormalism
2021
Interlacing families III: Sharper restricted invertibility estimates
Marcus A, Spielman D, Srivastava N. Interlacing families III: Sharper restricted invertibility estimates. Israel Journal Of Mathematics 2021, 247: 519-546. DOI: 10.1007/s11856-021-2277-z.Peer-Reviewed Original Research
2018
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
Marcus A, Spielman D, Srivastava N. Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. SIAM Journal On Computing 2018, 47: 2488-2509. DOI: 10.1137/16m106176x.Peer-Reviewed Original Research
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 ResearchSparsified Cholesky and multigrid solvers for connection laplacians
Kyng R, Lee Y, Peng R, Sachdeva S, Spielman D. Sparsified Cholesky and multigrid solvers for connection laplacians. 2016, 842-850. DOI: 10.1145/2897518.2897640.Peer-Reviewed Original ResearchSystem of equationsConnection LaplacianNonzero matrix entriesApproximate inverseLinear time algorithmMultigrid algorithmMultigrid solverLinear equationsLaplacian matrixGaussian eliminationGraph LaplacianMatrix entriesLU factorizationNonzero entriesStrong approximationOriginal matrixLinear numberEquationsLaplacianLinear timeTime algorithmNew algorithmAlgorithmCholeskyFactorization
2015
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
Marcus A, Spielman D, Srivastava N. Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. 2015, 1358-1377. DOI: 10.1109/focs.2015.87.Peer-Reviewed Original ResearchInterlacing families I: Bipartite Ramanujan graphs of all degrees
Marcus A, Spielman D, Srivastava N. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Annals Of Mathematics 2015, 307-325. DOI: 10.4007/annals.2015.182.1.7.Peer-Reviewed Original ResearchInterlacing families II: Mixed characteristic polynomials and the Kadison--Singer problem
Marcus A, Spielman D, Srivastava N. Interlacing families II: Mixed characteristic polynomials and the Kadison--Singer problem. Annals Of Mathematics 2015, 327-350. DOI: 10.4007/annals.2015.182.1.8.Peer-Reviewed Original Research
2014
An efficient parallel solver for SDD linear systems
Peng R, Spielman D. An efficient parallel solver for SDD linear systems. 2014, 333-342. DOI: 10.1145/2591796.2591832.Peer-Reviewed Original ResearchSystem of equationsEfficient parallel solverLinear systemsLinear equationsLow-stretch spanning treesSDD matrixDominant matricesParallel solverInput matrixSparse matricesFast algorithmPolylogarithmic timeParallel algorithmEquationsFirst parallel algorithmSpanning treeLinear workAlgorithmMatrixSparsifiersSolverInverseSystemNearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
Spielman D, Teng S. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal On Matrix Analysis And Applications 2014, 35: 835-885. DOI: 10.1137/090771430.Peer-Reviewed Original ResearchDiagonal entriesInverse power methodLinear system solverDominant linear systemsLower asymptotic complexityLinear systemsLinear time algorithmNonzero structureCondition numberSystem solverDominant matricesFiedler vectorNonzero entriesPreconditionerAsymptotic complexityDevelopment of algorithmsRandomized algorithmSpecial casePower methodIntroduction of algorithmsRecursive fashionTime algorithmAlgorithmMatrixSolverTwice-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
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Marcus A, Spielman D, Srivastava N. Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. 2013, 529-537. DOI: 10.1109/focs.2013.63.Peer-Reviewed Original ResearchSpectral 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 clustersA Cheeger Inequality for the Graph Connection Laplacian
Bandeira A, Singer A, Spielman D. A Cheeger Inequality for the Graph Connection Laplacian. SIAM Journal On Matrix Analysis And Applications 2013, 34: 1611-1630. DOI: 10.1137/120875338.Peer-Reviewed Original Research
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
An elementary proof of the restricted invertibility theorem
Spielman D, Srivastava N. An elementary proof of the restricted invertibility theorem. Israel Journal Of Mathematics 2011, 190: 83-91. DOI: 10.1007/s11856-011-0194-2.Peer-Reviewed Original ResearchElectrical 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 ResearchGraph Sparsification by Effective Resistances
Spielman D, Srivastava N. Graph Sparsification by Effective Resistances. SIAM Journal On Computing 2011, 40: 1913-1926. DOI: 10.1137/080734029.Peer-Reviewed Original Research