Papers of Daniel A. Spielman:

2012

A Cheeger Inequality for the Graph Connection Laplacian
http://arxiv.org/abs/1204.3873. 2012
With Afonso S. Bandeira and Amit Singer
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
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
Twice-Ramanujan Sparsifiers
STOC 2009. 2009
With Joshua Batson and Nikhil Srivastava
Invited to Special Issue of SICOMP
PDF
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

A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
http://arxiv.org/abs/0809.3232. 2008
With Shang-Hua Teng
Graph Sparsification by Effective Resistances
STOC '08. 2008
With Nikhil Srivastava
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

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
http://www.arxiv.org/abs/cs.NA/0607105. 2006
With Shang-Hua Teng
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

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