Daniel Alan Spielman
Sterling Professor of Computer Science and Professor of Statistics and Data Science and of MathematicsCards
About
Research
Publications
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 algorithmAlgorithmMatrixSolver