# Daniel Spielman

#5,921

Most Influential Person Now

American computer scientist

## Daniel Spielman's AcademicInfluence.com Rankings

Daniel Spielmancomputer-science Degrees

Computer Science

#772

World Rank

#798

Historical Rank

#417

USA Rank

Machine Learning

#2163

World Rank

#2191

Historical Rank

#129

USA Rank

Database

#4323

World Rank

#4496

Historical Rank

#693

USA Rank

## Download Badge

Computer Science

## Why Is Daniel Spielman Influential?

(Suggest an Edit or Addition)According to Wikipedia, Daniel Alan Spielman has been a professor of applied mathematics and computer science at Yale University since 2006. As of 2018, he is the Sterling Professor of Computer Science at Yale. He is also the Co-Director of the Yale Institute for Network Science, since its founding, and chair of the newly established Department of Statistics and Data Science.

## Daniel Spielman's Published Works

### Published Works

- Efficient erasure correcting codes (2001) (1237)
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems (2003) (934)
- Expander codes (1994) (933)
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time (2001) (891)
- Graph sparsification by effective resistances (2008) (878)
- Improved low-density parity-check codes using irregular graphs (2001) (842)
- Practical loss-resilient codes (1997) (796)
- Exponential algorithmic speedup by a quantum walk (2002) (793)
- Spectral Graph Theory and its Applications (2007) (614)
- Spectral partitioning works: planar graphs and finite element meshes (1996) (602)
- Twice-ramanujan sparsifiers (2008) (513)
- Interlacing families II: Mixed characteristic polynomials and the Kadison{Singer problem (2013) (490)
- Spectral Sparsification of Graphs (2008) (473)
- Linear-time encodable and decodable error-correcting codes (1995) (419)
- Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems (2006) (398)
- Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (2013) (367)
- Analysis of low density codes and improved designs using irregular graphs (1998) (344)
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning (2008) (342)
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs (2010) (325)
- Exact Recovery of Sparsely-Used Dictionaries (2012) (241)
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices (2003) (232)
- Lower-stretch spanning trees (2004) (213)
- Randomness efficient identity testing of multivariate polynomials (2001) (205)
- PP is closed under intersection (1991) (190)
- Nearly-linear size holographic proofs (1994) (186)
- An efficient parallel solver for SDD linear systems (2013) (177)
- Smoothed analysis: an attempt to explain the behavior of algorithms in practice (2009) (174)
- Spectral sparsification of graphs: theory and algorithms (2013) (172)
- Improved low-density parity-check codes using irregular graphs and belief propagation (1998) (166)
- The Smoothed Analysis of Algorithms (2002) (164)
- Faster approximate lossy generalized flow via interior point algorithms (2008) (161)
- Sparsified Cholesky and multigrid solvers for connection laplacians (2015) (151)
- Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices (2011) (148)
- A Cheeger Inequality for the Graph Connection Laplacian (2012) (129)
- Fitting a graph to vector data (2009) (128)
- A Lower Bound on Convergence of a Distributed Network Consensus Algorithm (2005) (118)
- An elementary proof of the restricted invertibility theorem (2009) (107)
- Faster isomorphism testing of strongly regular graphs (1996) (91)
- Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes (2015) (84)
- A randomized polynomial-time simplex algorithm for linear programming (2006) (84)
- Accelerated Gossip Algorithms for Distributed Computation (2006) (74)
- The perceptron strikes back (1991) (72)
- Algorithms for Lipschitz Learning on Graphs (2015) (66)
- Computationally efficient error-correcting codes and holographic proofs (1995) (66)
- Spectral Graph Theory (2012) (64)
- Highly fault-tolerant parallel computation (1996) (63)
- A Remark on Matrix Rigidity (1997) (61)
- Disk packings and planar separators (1996) (57)
- Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m1.31) (2003) (55)
- Smoothed analysis of termination of linear programming algorithms (2003) (54)
- An Infinite Antichain of Permutations (1998) (52)
- A Note on Preconditioning by Low-Stretch Spanning Trees (2009) (49)
- Introduction to the special issue on codes on graphs and iterative algorithms (2001) (45)
- Parallel Delaunay Refinement: Algorithms and Analyses (2002) (42)
- Solving sparse, symmetric, diagonally-dominant linear systems in time O(m/sup 1.31/ (2003) (42)
- Ramanujan Graphs and the Solution of the Kadison-Singer Problem (2014) (39)
- Smoothed Analysis (Motivation and Discrete Models) (2003) (39)
- Facility location and the analysis of algorithms through factor-revealing programs (2004) (37)
- Smoothed Analysis of Renegar’s Condition Number for Linear Programming (2002) (37)
- Fault diagnosis in a small constant number of parallel testing rounds (1993) (34)
- Spectral sparsification and restricted invertibility (2010) (33)
- The Minimum Distance of Turbo-Like Codes (2009) (31)
- Sparsified Cholesky Solvers for SDD linear systems (2015) (27)
- Alternation in interaction (1994) (26)
- Finite free convolutions of polynomials (2015) (26)
- Improved smoothed analysis of the shadow vertex simplex method (2005) (22)
- Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (1999) (21)
- Smoothed analysis of condition numbers and complexity implications for linear programming (2011) (19)
- Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations (2012) (18)
- The power of adaptiveness and additional queries in random-self-reductions (1992) (18)
- The Complexity of Error-Correcting Codes (1997) (17)
- Support-Graph Preconditioners for 2-Dimensional Trusses (2007) (16)
- Time complexity of practical parallel steiner point insertion algorithms (2004) (14)
- Balancing covariates in randomized experiments with the Gram-Schmidt Walk design (2019) (14)
- Graphs, Vectors, and Matrices (2016) (14)
- Min-max-boundary domain decomposition (1998) (12)
- Constructing Error-Correcting Codes from Expander Graphs (1999) (11)
- Interlacing families III: Sharper restricted invertibility estimates (2017) (11)
- Foundations of Computational Mathematics, Santander 2005: Smoothed Analysis of Algorithms and Heuristics (2006) (10)
- Parallel Delaunay Refinement with Off-Centers (2004) (7)
- The Kadison-Singer problem (2014) (7)
- A complexity theoretic approach to learning (2002) (6)
- Smoothed Analysis of Interior-Point Algorithms: Termination (2003) (6)
- Smoothed Analysis of Interior-Point Algorithms: Condition Number (2003) (6)
- PP Is Closed Under Intersection (Extended Abstract) (1991) (5)
- Conductance, the Normalized Laplacian, and Cheeger's Inequality (2015) (4)
- Proceedings of the 44th Annual Allerton Conference on Communication, Control, and Computation (2006) (4)
- The Perceptron Strikes Back* preliminary report (1991) (3)
- The Adjacency Matrix and The n th Eigenvalue (2012) (3)
- Models of computation in coding theory (1998) (3)
- Linear-Time Encodable Error-Correcting Codes Decodable (3)
- Spectral Graph Theory Lecture 5 The other eigenvectors of the Laplacian (2009) (3)
- Spectral Graph Theory and Its Applications 7.1 Random Walks on Weighted Graphs (2004) (3)
- Hardness Results for Weaver's Discrepancy Problem (2022) (2)
- A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix (2009) (2)
- Highly Fault-Tolerant Parallel Computation Extended Abstract* (1996) (2)
- Spectral Graph Theory Lecture 24 Strongly Regular Graphs , part 2 (2009) (2)
- Spectral Partitiong in a Stochastic Block Model (2015) (2)
- Spectral Partitioning Works : Planar graphs and nite element meshes Preliminary Draft (1997) (2)
- Exact Recovery of Sparse-Used Dictionaries (2013) (2)
- On -Dual Binary Codes (2007) (2)
- Erdös-Rényi Random Graphs : Warm Up (2010) (1)
- 6.1 Introduction (2004) (1)
- Spectral Graph Theory and Its Applications 6.1 Adjacency Matrices, Random Walks, and Expander Graphs 6.2 Expander Graphs (2004) (1)
- Tutte's Theorem (2015) (1)
- Lecture notes from IPCO Summer School 2005 Fast Randomized Algorithms for Partitioning, Sparsification, and Solving Linear Systems (2005) (1)
- Spectral Graph Theory Lecture 22 Expected Characteristic Polynomials (2015) (1)
- Graph Constructions for Machine Learning Optimization and Combinatorial Properties (2011) (1)
- Testing Isomorphism of Graphs with Distinct Eigenvalues (2009) (1)
- Fast Approximation of Maximum Flow using Electrical Flows (2011) (1)
- Graph Construction Through Laplacian Function Optimization (2011) (1)
- Courant-Fischer and Graph Coloring (2009) (1)
- Spectral Partitioning in the Planted Partition Model (2009) (1)
- The Adjacency Matrix and Graph Coloring (2015) (1)
- Implementing Spectral Methods for Multiway Sparse Cuts (2013) (0)
- Error-Correcting Codes Decodable (1996) (0)
- 7.1 Developments in Iterative Decoding 17.2 Achieving Capacity on the Bec (2004) (0)
- Graph Sparsification Techniques (2007) (0)
- Concentration of Measure from Eigenvalue Bounds (2012) (0)
- Lecture 4 a Gaussian Elimination Example (2002) (0)
- University of Groningen Accelerated Gossip Algorithms for Distributed Computation (2007) (0)
- Spectral Graph Theory and Its Applications 5.1 Introduction (0)
- Laplacian and the Adjacency Matrices (2009) (0)
- Graphs and Networks Lecture 6 Spectral Partitioning (2007) (0)
- Implementation and Testing of Algorithm for Computing Effective Resistances Between Vertices in Graphs (2010) (0)
- Exploring algorithms for finding low-stretch spanning trees (2018) (0)
- Graphs and Networks Lecture 15 The Giant Component (2006) (0)
- Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009) (2013) (0)
- 7 . 1 Random Walks on Weighted Graphs (2004) (0)
- Bipartite Ramanujan Graphs (2018) (0)
- A Batchwise Monotone Algorithm for Dictionary Learning (2015) (0)
- Graph Sparsification Heuristics (2008) (0)
- Smoothed Analysis of Renegar ' s Condition Numberfor Linear (2002) (0)
- CPSC 490 : Solving Ill-Conditioned Laplacian Systems in Theory and Practice (2018) (0)
- Spectral Graph Theory Lecture 5 Cayley Graphs (2009) (0)
- Parallel Decoding of expander codes (2018) (0)
- Space-Time Tradeoffs for Graph Properties by Yevgeniy Dodis (0)
- J ul 2 01 9 FINITE FREE CONVOLUTIONS VIA WEINGARTEN CALCULUS (2019) (0)
- Planar Graphs 2 , the Colin de Verdière Number (2009) (0)
- Space-time Tradeoos for Graph Properties Space-time Tradeoos for Graph Properties (1999) (0)
- Fitting a graph to vector data Citation (2009) (0)
- Discovering and Analyzing Network Function and Structure (2015) (0)
- Lecture 19 Last Time We Proved How Smooth Are Gaussians (2002) (0)
- Personal PageRank and Spilling Paint (2010) (0)
- Chapter 16 Spectral Graph Theory (2010) (0)
- HEAVY TALED SERIES OF REDUNDANT LAYERS (2017) (0)
- Dynamic and Nonlinear Networks (2013) (0)
- Multi-way Graph Partitioning using Network Flow (2009) (0)
- Graphs and Networks Lecture 5 The Giant Component and Diameter (2010) (0)
- Iterative Algorithms for Lipschitz Learning on Graphs (2015) (0)
- Implementing Multiway Spectral Partitioning (2013) (0)
- Interior-Point Methods with Laplacian Linear Solvers (2015) (0)
- CS 490 Final Report (2018) (0)
- The Second Eigenvalue of Planar Graphs (2015) (0)
- Evolving Sets and Their Applications to Local Graph Partitioning (2011) (0)
- Sampling Weighted Edges with Proportional Probability (2018) (0)
- Spectral Graph Theory Lecture 7 Cheeger ’ s Inequality (2009) (0)
- Graphs and Networks Lecture 6 Percolation I (2013) (0)
- Spectral Graph Theory Lecture 19 Diameter , Probability , and Concentration of Measure (2009) (0)
- Robust and Practical Solution of Laplacian Equations by Approximate Elimination (2023) (0)
- Algorithmic Discrepancy in the Wild (2019) (0)
- 17 . 1 Developments in iterative decoding (0)
- Quadrature for the Finite Free Convolution (2015) (0)
- Graph Decomposition and Applications to Low-Stretch Spanning Trees (2017) (0)
- An elementary proof of the restricted invertibility theorem (2011) (0)
- High-Frequency Eigenvalues (2018) (0)
- Erdös-Rényi Random Graphs : The Giant Component (2010) (0)
- Technical perspectiveThe beauty of error-correcting codes (2009) (0)
- Expander Codes 12.1 Overview 12.2 Bipartite Expander Graphs (2009) (0)
- CS490 Senior Thesis Proposal (2018) (0)
- Graphs and Networks Lecture 8 Random Walks and Diffusion (2010) (0)
- 18.405J / 6.841J Advanced Complexity Theory, Fall 2001 (2001) (0)
- Planar Graphs, Part 1 25.1 Introduction (2009) (0)
- Cutting Graphs , Personal PageRank and Spilling Paint (2010) (0)
- The Beauty of Error-Correcting Codes (2009) (0)
- Convergence of Random Walks and Conductance-Draft (2013) (0)
- 2002 Information Theory Society Paper Award (2001) (0)

This paper list is powered by the following services:

## Other Resources About Daniel Spielman

## What Schools Are Affiliated With Daniel Spielman?

Daniel Spielman is affiliated with the following schools: