List of Papers by Topic

Smoothed Analysis

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
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
Smoothed Analysis: Motivation and Discrete Models
Proceedings of WADS 2003, Lecture Notes in Computer Science 2748, pp. 256-270. 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 of Renegar's Condition Number for Linear Programming
Available at http://arxiv.org/abs/cs.DS/0302011. Submitted for publication.. 2003
With John D. Dunagan and Shang-Hua Teng
Smoothed Analysis of Algorithms
Proceedings of the International Congress of Mathematicians, vol I, pp. 597-606. 2002
With Shang-Hua Teng

Combinatorial Scientific Computing

Faster Approximate Lossy Generalized Flow via Interior Point Algorithms
STOC '08. 2008
With Samuel I. Daitch
Graph Sparsification by Effective Resistances
STOC '08. 2008
With Nikhil Srivastava
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
Spectral Sparsification of Graphs
http://arxiv.org/abs/0808.4134. 2008
With Shang-Hua Teng
Twice-Ramanujan Sparsifiers
http://arxiv.org/abs/0808.0163. 2008
With Joshua Batson and Nikhil Srivastava
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
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
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
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
Parallel Delaunay Refinement with Off-Centers
10th International EURO-PAR Conference, pp. 812--819. 2004
With Shang-Hua Teng and Alper Ungor
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
Parallel Delaunay Refinement
Proceedings of the 11th International Meshing Roundtable. Submitted for publication.. 2002
With Shang-Hua Teng and Alper Ungor
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
Disk Packings and Planar Separators
SCG 96: 12th Annual ACM Symposium on Computational Geometry, pages 349-358. 1996
With Shang-Hua Teng

Other papers on Algorithms

Lower-Stretch Spanning Trees
SIAM Journal on Computing, Vol 32 (2), pp. 608--628. 2008
With Michael Elkin, Yuval Emek and Shang-Hua Teng
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
Randomness Efficient Identity Testing
Proceedings of the 33rd Symposium on Theory of Computing. 2001
With Adam R. Klivans
Faster Isomorphism Testing of Strongly Regular Graphs
28th Annual ACM Symposium on Theory of Computing, pages 576-584. 1996

Error-Correcting Codes

The Minimum Distance of Turbo-Like Codes
Submitted to the IEEE Transaction on Information Theory. 2003
With Louay Bazzi and Mohammad Mahdian
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
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
Finding good LDPC codes
Proceedings of the 36th Annual Allerton Conference on Communication, Control, and Computing . 1998
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
Constructing Error-Correcting Codes from Expander Graphs
Emerging Applications of Number Theory, IMA volumes in mathematics and its applications, vol 109. 1996
Expander Codes
IEEE Transactions on Information Theory, , Vol 42, No 6, pp. 1710-1722. 1996
With Michael Sipser
Linear-time encodable and decodable error-correcting codes
IEEE Transactions on Information Theory, , Vol 42, No 6, pp. 1723-1732. 1996

Computational Complexity

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
Alternation in Interaction
Computational Complexity, 9(3-4):202-246. 2000
With Marcos Kiwi, Carsten Lund, Alex Russell and Ravi Sundaram
A Remark on Matrix Rigidity
Information Processing Letters, 64(6), pp. 283--285. 1997
With M. Amin Shokrollahi and Voelker Stemann
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
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
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 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

Fault Tolerance

Highly Fault-Tolerant Parallel Computation
Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, pp. 154-163. 1996
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

Miscellaneous

Accelerated Gossip Algorithms for Distributed Computation
44th Annual Allerton Conference on Communication, Control, and Computation. 2006
With Ming Cao and Edmund Yeh
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