Papers of Daniel A. Spielman:

2023

Robust and Practical Solution of Laplacian Equations by Approximate Elimination
https://arxiv.org/abs/2303.00709. 2023
With Yuan Gao and Rasmus Kyng
PDF
Balancing Covariates in Randomized Experiments with the Gram-Schmidt Walk Design
Journal of the American Statistical Association. 2023
With Christopher Harshaw, Fredrik Savje and Peng Zhang
PDF
Julia code: GSWDesign.jl
The arxiv version, with the paper and all supplements in one file

2022

Hardness Results for Weaver's Discrepancy Problem
LIPIcs, Volume 245, Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). 2022
With Peng Zhang
PDF
ArXiv version
Interlacing Families III: Sharper Restricted Invertibility Estimates
Israel Journal of Mathematics volume 247, pages 519–546. 2022
With Adam W. Marcus and Nikhil Srivastava
PDF
arXiv version
Finite free convolutions of polynomials
Probability Theory and Related Fields volume 182, pages 807–848. 2022
With Adam Marcus and Nikhil Srivastava
PDF
arXiv version

2019

Spectral and Algebraic Graph Theory
Book in progress. 2019
PDF

2018

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
SIAM Journal on Computing, Vol 47, no. 6. 2488-2509. 2018
With Adam W. Marcus and Nikhil Srivastava
PDF

2017

Graphs, Vectors, and Matrices
Bulletin (New Series) of the American Mathematical Society, Vol. 54, no. 1, pp. 45-61. 2017
PDF

2016

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
ACM STOC. 2016
With Rasmus Kyng, Yin Tat Lee, Richard Peng and Sushant Sachdeva
PDF

2015

Algorithms for Lipschitz Learning on Graphs
COLT. 2015
With Rasmus Kyng, Anup Rao and Sushant Sachdeva
PDF
Code on github
Sparsified Cholesky Solvers for SDD linear systems
http://arxiv.org/abs/1506.08204. 2015
With Yin Tat Lee and Richard Peng
PDF
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Annals of Mathematics, 182 (1), pp. 307-325. 2015
With Adam Marcus and Nikhil Srivastava
PDF
There was an earlier version on arXiv, of which the journal paper is a slight improvement
Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem
Annals of Mathematics, 182 (1), pp. 327-350. 2015
With Adam Marcus and Nikhil Srivastava
PDF
An earlier version appeared on arXiv

2014

Ramanujan Graphs and the Solution of the Kadison-Singer Problem
Proceedings of the 2014 International Congress of Mathematicians, vol. 3, pp. 363-386.. 2014
With Adam W. Marcus and Nikhil Srivastava
Twice-Ramanujan Sparsifiers (Sigest)
SIAM Review, Vol. 56, Issue 2, pp. 315-334. 2014
With Joshua Batson and Nikhil Srivastava
PDF
An Efficient Parallel Solver for SDD Linear Systems
STOC 2014. 2014
With Richard Peng
PDF
Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
SIAM J. Matrix Anal. & Appl. 35-3, pp. 835-885. 2014
With Shang-Hua Teng
PDF
This page contains links to related papers.

2013

Spectral Sparsification of Graphs: Theory and Algorithms
Communications of the ACM, Vol. 56 No. 8, Pages 87-94. 2013
With Josh Batson, Nikhil Srivastava and Shang-Hua Teng
PDF
Technical Perspective by Assaf Naor
A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
SIAM Journal on Computing, vol 42 (1), pp. 1-26. 2013
With Shang-Hua Teng
PDF
A page related to this and related work
A Cheeger Inequality for the Graph Connection Laplacian
SIAM Journal on Matrix Analysis, Vol. 24, Issue 4, pp. 1611-1630. 2013
With Afonso S. Bandeira and Amit Singer
PDF

2012

Twice-Ramanujan Sparsifiers
SICOMP, Vol 41, Number 6, pp. 1704-1721. 2012
With Joshua Batson and Nikhil Srivastava
PDF
Exact Recovery of Sparsely-Used Dictionaries
Conference on Learning Theory. 2012
With Huan Wang and John Wright
Won award for best paper.
PDF

2011

Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
In Proceedings of STOC 2011.. 2011
With Paul Christiano, Jonathan A. Kelner, Aleksander Madry and Shang-Hua Teng
Shared award for best paper
Graph Sparsification by Effective Resistances
SIAM Journal on Computing, Vol. 40, No. 6, pp. 1913-1926. 2011
With Nikhil Srivastava
Conference version appeared in STOC '08
PDF
Spectral Sparsification of Graphs
SIAM Journal on Computing, vol. 40, pp. 981-1025. 2011
With Shang-Hua Teng
My page about this and the related papers.
Spectral Graph Theory
to appear in Combinatorial Scientific Computing. Chapman and Hall/CRC Press. 2011
PDF

2010

Algorithms, Graph Theory, and Linear Equations
Proceedings of the International Congress of Mathematicians, vol IV, pp. 2698--2722.. 2010

2009

Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice
Communications of the ACM, Oct 2009, pp. 76-84. 2009
With Shang-Hua Teng
PDF
An Elementary Proof of the Restricted Invertibility Theorem
To appear in the Israeli Journal of Mathematics. 2009
With Nikhil Srivastava
Fitting a Graph to Vector Data
ICML. 2009
With Jon Kelner and Sam Daitch
A Note on Preconditioning by Low-Stretch Spanning Trees
http://arxiv.org/abs/0903.2816. 2009
With Jaeoh Woo
Smoothed analysis of condition numbers and complexity implications for linear programming
Mathematical Programming, Series A,. 2009
With John D. Dunagan and Shang-Hua Teng
Previously appeared as Smoothed Analysis of Renegar's Condition Number for Linear Programming
PDF
The Minimum Distance of Turbo-Like Codes
IEEE Transactions on Information Theory, Vol 55, Issue 1, Jan 2009, pages 6-15. 2009
With Louay Bazzi and Mohammad Mahdian
PDF
The beauty of error-correcting codes
Communications of the ACM, March 2009, page 86. 2009
PDF

2008

Faster Approximate Lossy Generalized Flow via Interior Point Algorithms
STOC '08. 2008
With Samuel I. Daitch
Lower-Stretch Spanning Trees
SIAM Journal on Computing, Vol 32 (2), pp. 608--628. 2008
With Michael Elkin, Yuval Emek and Shang-Hua Teng

2007

Parallel Delaunay Refinement: Algorithms and Analyses
International Journal of Computational Geometry & Applications, Vol. 17, No. 1 (2007) 1-30. 2007
With Shang-Hua Teng and Alper Ungor
Support-Graph Preconditioners for 2-Dimensional Trusses
http://arxiv.org/abs/cs/0703119. 2007
With Samuel I. Daitch
Spectral Partitioning Works: Planar graphs and finite element meshes
Linear Algebra and its Applications Volume 421, Issues 2-3, 1 March 2007, Pages 284-305. 2007
With Shang-Hua Teng

2006

Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
SIMAX Volume 28, Issue 2, pp. 446-476. 2006
With Arvind Sankar and Shang-Hua Teng
PDF
Accelerated Gossip Algorithms for Distributed Computation
44th Annual Allerton Conference on Communication, Control, and Computation. 2006
With Ming Cao and Edmund Yeh
PDF
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming
Proceedings of the 38th annual ACM symposium on Theory of computing. 2006
With Jonathan A. Kelner

2005

A Lower Bound on Convergence of a Distributed Network Consensus Algorithm
44th IEEE Conference on Decision and Control. 2005
With Ming Cao and Stephen Morse

2004

Smoothed Analysis of Algorithms: Why The Simplex Algorithm Usually Takes Polynomial Time
Journal of the ACM, Vol 51 (3), pp. 385 - 463. 2004
With Shang-Hua Teng
Parallel Delaunay Refinement with Off-Centers
10th International EURO-PAR Conference, pp. 812--819. 2004
With Shang-Hua Teng and Alper Ungor
Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 81--90. 2004
With Shang-Hua Teng

2003

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^{1.31})
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 416-427. 2003
With Shang-Hua Teng
Smoothed Analysis of Termination of Linear Programming Algorithms
Mathematical Programming, Series B, Vol 97, pp. 375-404. 2003
With Shang-Hua Teng
Smoothed Analysis: Motivation and Discrete Models
Proceedings of WADS 2003, Lecture Notes in Computer Science 2748, pp. 256-270. 2003
With Shang-Hua Teng
Exponential algorithmic speedup by a quantum walk
Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, pp. 59-68. 2003
With Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi and Sam Gutmann

2002

Parallel Delaunay Refinement
Proceedings of the 11th International Meshing Roundtable. Submitted for publication.. 2002
With Shang-Hua Teng and Alper Ungor
Smoothed Analysis of Algorithms
Proceedings of the International Congress of Mathematicians, vol I, pp. 597-606. 2002
With Shang-Hua Teng
Our personal version of the paper.

2001

Improved Low-Density Parity-Check Codes Using Irregular Graphs
IEEE Transactions on Information Theory, 47(2), pp. 585-598. 2001
With Michael G. Luby, Michael Mitzenmacher and M. Amin Shokrollahi
PDF
Efficient Erasure Correcting Codes
IEEE Transactions on Information Theory, 47(2), pp. 569-584. 2001
With Michael G. Luby, Michael Mitzenmacher and M. Amin Shokrollahi
PDF
Min-Max-Boundary Domain Decomposition
Special issue of Theoretical Computer Science for COCOON'98, volume 261, issue 2, pp. 253-266. 2001
With Marcos Kiwi and Shang-Hua Teng
Randomness Efficient Identity Testing
Proceedings of the 33rd Symposium on Theory of Computing. 2001
With Adam R. Klivans

2000

Alternation in Interaction
Computational Complexity, 9(3-4):202-246. 2000
With Marcos Kiwi, Carsten Lund, Alex Russell and Ravi Sundaram

1998

Finding good LDPC codes
Proceedings of the 36th Annual Allerton Conference on Communication, Control, and Computing . 1998

1997

A Remark on Matrix Rigidity
Information Processing Letters, 64(6), pp. 283--285. 1997
With M. Amin Shokrollahi and Voelker Stemann
The complexity of error-correcting codes
Plenary lecture at the 11th International Symposium on Fundamentals of Computation Theory, Krakow, Poland, Lecture Notes in Computer Science #1279, pp. 67-84. 1997

1996

Linear-time encodable and decodable error-correcting codes
IEEE Transactions on Information Theory, Vol 42, No 6, pp. 1723-1732. 1996
PDF
Expander Codes
IEEE Transactions on Information Theory, , Vol 42, No 6, pp. 1710-1722. 1996
With Michael Sipser
Faster Isomorphism Testing of Strongly Regular Graphs
28th Annual ACM Symposium on Theory of Computing, pages 576-584. 1996
Highly Fault-Tolerant Parallel Computation
Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, pp. 154-163. 1996
Disk Packings and Planar Separators
SCG 96: 12th Annual ACM Symposium on Computational Geometry, pages 349-358. 1996
With Shang-Hua Teng
Constructing Error-Correcting Codes from Expander Graphs
Emerging Applications of Number Theory, IMA volumes in mathematics and its applications, vol 109. 1996

1995

Thesis: Computationally Efficient Error-Correcting Codes and Holographic Proofs
My thesis, M.I.T. Department of Mathematics. 1995
PP is closed under intersection
Journal of Computer and System Sciences, vol. 50, no. 2, pp. 191-202. 1995
With Richard Beigel and Nick Reingold

1994

Nearly linear-size holographic proofs
Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pp. 194-203. 1994
With Alexander Polishchuk
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions
Computational Complexity, vol. 4, pp. 158-174. 1994
With Joan Feigenbaum, Lance Fortnow and Carsten Lund

1993

Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures. 1993
With Richard Beigel and Grigorii Margulis

1991

The Perceptron Strikes Back
Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory, pp. 286-291. 1991
With Richard Beigel and Nick Reingold