Daniel A. Spielman

CoRR, 2023

2022

Hardness Results for Weaver's Discrepancy Problem.

[BibT_eX]

[DOI]

Peng Zhang

Proceedings of the Approximation, 2022

2019

Balancing covariates in randomized experiments using the Gram-Schmidt walk.

[BibT_eX]

[DOI]

CoRR, 2019

2018

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes.

[BibT_eX]

[DOI]

Adam W. Marcus

SIAM J. Comput., 2018

2016

Sparsified Cholesky and multigrid solvers for connection laplacians.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

A Batchwise Monotone Algorithm for Dictionary Learning.

[BibT_eX]

[DOI]

Huan Wang

John Wright

CoRR, 2015

Sparsified Cholesky Solvers for SDD linear systems.

[BibT_eX]

[DOI]

Yin Tat Lee

Richard Peng

CoRR, 2015

Algorithms for Lipschitz Learning on Graphs.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Twice-Ramanujan Sparsifiers.

[BibT_eX]

[DOI]

Joshua D. Batson

SIAM Rev., 2014

Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems.

[BibT_eX]

[DOI]

SIAM J. Matrix Anal. Appl., 2014

An efficient parallel solver for SDD linear systems.

[BibT_eX]

[DOI]

Richard Peng

Proceedings of the Symposium on Theory of Computing, 2014

2013

A Cheeger Inequality for the Graph Connection Laplacian.

[BibT_eX]

[DOI]

Afonso S. Bandeira

Amit Singer

SIAM J. Matrix Anal. Appl., 2013

A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009).

[BibT_eX]

[DOI]

Maria-Florina Balcan

Mark Braverman

SIAM J. Comput., 2013

Spectral sparsification of graphs: theory and algorithms.

[BibT_eX]

[DOI]

Commun. ACM, 2013

Exact Recovery of Sparse-Used Dictionaries.

[BibT_eX]

[DOI]

Huan Wang

John Wright

Proceedings of the IJCAI 2013, 2013

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees.

[BibT_eX]

[DOI]

Adam Marcus

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Exact Recovery of Sparsely-Used Dictionaries.

[BibT_eX]

[DOI]

Huan Wang

John Wright

Proceedings of the COLT 2012, 2012

Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Spectral Sparsification of Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Graph Sparsification by Effective Resistances.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Smoothed analysis of condition numbers and complexity implications for linear programming.

[BibT_eX]

[DOI]

John Dunagan

Math. Program., 2011

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2009

The Minimum Distance of Turbo-Like Codes.

[BibT_eX]

[DOI]

Louay Bazzi

Mohammad Mahdian

IEEE Trans. Inf. Theory, 2009

A Note on Preconditioning by Low-Stretch Spanning Trees

[BibT_eX]

[DOI]

Jaeoh Woo

CoRR, 2009

Smoothed analysis: an attempt to explain the behavior of algorithms in practice.

[BibT_eX]

[DOI]

Commun. ACM, 2009

Technical perspective - The beauty of error-correcting codes.

[BibT_eX]

[DOI]

Commun. ACM, 2009

Fitting a graph to vector data.

[BibT_eX]

[DOI]

Jonathan A. Kelner

Proceedings of the 26th Annual International Conference on Machine Learning, 2009

A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Scientific Computing, 01.02. - 06.02.2009, 2009

2008

Lower-Stretch Spanning Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Faster approximate lossy generalized flow via interior point algorithms.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Parallel Delaunay Refinement: Algorithms and Analyses.

[BibT_eX]

[DOI]

Alper Üngör

Int. J. Comput. Geom. Appl., 2007

Support-Graph Preconditioners for 2-Dimensional Trusses

[BibT_eX]

[DOI]

CoRR, 2007

Spectral Graph Theory and its Applications.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices.

[BibT_eX]

[DOI]

Arvind Sankar

SIAM J. Matrix Anal. Appl., 2006

A randomized polynomial-time simplex algorithm for linear programming.

[BibT_eX]

[DOI]

Jonathan A. Kelner

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

[BibT_eX]

[DOI]

Jonathan A. Kelner

Electron. Colloquium Comput. Complex., 2005

Improved Smoothed Analysis of the Shadow Vertex Simplex Method.

[BibT_eX]

[DOI]

Amit Deshpande

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

The Smoothed Analysis of Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

A Lower Bound on Convergence of a Distributed Network Consensus Algorithm.

[BibT_eX]

[DOI]

Ming Cao

A. Stephen Morse

Proceedings of the 44th IEEE IEEE Conference on Decision and Control and 8th European Control Conference Control, 2005

2004

Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.

[BibT_eX]

[DOI]

J. ACM, 2004

Lower-Stretch Spanning Trees

[BibT_eX]

[DOI]

Michael Elkin

CoRR, 2004

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Time complexity of practical parallel steiner point insertion algorithms.

[BibT_eX]

[DOI]

Alper Üngör

Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Parallel Delaunay Refinement with Off-Centers.

[BibT_eX]

[DOI]

Alper Üngör

Proceedings of the Euro-Par 2004 Parallel Processing, 2004

2003

Smoothed analysis of termination of linear programming algorithms.

[BibT_eX]

[DOI]

Math. Program., 2003

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m<sup>1.31</sup>)

[BibT_eX]

[DOI]

CoRR, 2003

Smoothed Analysis of Interior-Point Algorithms: Condition Number

[BibT_eX]

[DOI]

John Dunagan

CoRR, 2003

Smoothed Analysis of Interior-Point Algorithms: Termination

[BibT_eX]

[DOI]

CoRR, 2003

Smoothed Analysis (Motivation and Discrete Models).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

Exponential algorithmic speedup by a quantum walk.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m<sup>1.31</sup>).

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001

Improved low-density parity-check codes using irregular graphs.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2001

Efficient erasure correcting codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2001

Introduction to the special issue on codes on graphs and iterative algorithms.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2001

Min-max-boundary domain decomposition.

[BibT_eX]

[DOI]

Marcos A. Kiwi

Theor. Comput. Sci., 2001

Randomness efficient identity testing of multivariate polynomials.

[BibT_eX]

[DOI]

Adam R. Klivans

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

An Infinite Antichain of Permutations.

[BibT_eX]

[DOI]

Miklós Bóna

Electron. J. Comb., 2000

Alternation in interaction.

[BibT_eX]

[DOI]

Comput. Complex., 2000

1998

Analysis of Low Density Codes and Improved Designs Using Irregular Graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Models of Computation in Coding Theory.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

A Remark on Matrix Rigidity.

[BibT_eX]

[DOI]

Volker Stemann

Inf. Process. Lett., 1997

Practical Loss-Resilient Codes.

[BibT_eX]

[DOI]

Volker Stemann

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

The Complexity of Error-Correcting Codes.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

1996

Linear-time encodable and decodable error-correcting codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1996

Expander codes.

[BibT_eX]

[DOI]

Michael Sipser

IEEE Trans. Inf. Theory, 1996

Faster Isomorphism Testing of Strongly Regular Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Spectral Partitioning Works: Planar Graphs and Finite Element Meshes.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Highly Fault-Tolerant Parallel Computation (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Disk Packings and Planar Separators.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995

PP Is Closed under Intersection.

[BibT_eX]

[DOI]

Nick Reingold

J. Comput. Syst. Sci., 1995

1994

The Power of Adaptiveness and Additional Queries in Random-Self-Reductions.

[BibT_eX]

[DOI]

Comput. Complex., 1994

Nearly-linear size holographic proofs.

[BibT_eX]

[DOI]

Alexander Polishchuk

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

Fault Diagnosis in a Small Constant Number of Parallel Testing Rounds.

[BibT_eX]

[DOI]

Grigorii Margulis

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

1991

PP Is Closed Under Intersection (Extended Abstract)

[BibT_eX]

[DOI]

Nick Reingold

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

The Perceptron Strikes Back.

[BibT_eX]

[DOI]

Nick Reingold