Daniel Alan Spielman
Cards
About
Titles
Sterling Professor of Computer Science and Professor of Statistics and Data Science and of Mathematics
ProfessorBiography
Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoctoral Fellow in the Computer Science Department at U.C. Berkeley, and then became a professor in the Applied Mathematics Department at M.I.T. He moved to Yale University in 2006, where he is the Sterling Professor of Computer Science, and Professor of Statistics and Data Science, and of Mathematics.
He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 and 2015 Godel Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, the 2014 Polya Prize, an inaugural Simons Investigator Award, and a MacArthur Fellowship. He is a Fellow of the Association for Computing Machinery and a member of the National Academy of Sciences and the Connecticut Academy of Science and Engineering. His main research interests include the design and analysis of algorithms, network science, machine learning, digital communications and scientific computing.
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