2005
Improved Smoothed Analysis of the Shadow Vertex Simplex Method
Deshpande A, Spielman D. Improved Smoothed Analysis of the Shadow Vertex Simplex Method. 2005, 349-356. DOI: 10.1109/sfcs.2005.44.Peer-Reviewed Original ResearchSmoothed complexityShadow vertex simplex methodParameter of perturbationNumber of constraintsSmoothed analysisGeometric resultsNumber of variablesLinear programVertex methodLinear programmingSimple proofSimplex methodRunning timeMultiplicative factorExponentSpielmanPolytopeProofComplexityVerticesPerturbations
2004
Time complexity of practical parallel steiner point insertion algorithms
Spielman D, Teng S, Üngör A. Time complexity of practical parallel steiner point insertion algorithms. 2004, 267-268. DOI: 10.1145/1007912.1007953.Peer-Reviewed Original Research
2003
Smoothed analysis of termination of linear programming algorithms
Spielman D, Teng S. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming 2003, 97: 375-404. DOI: 10.1007/s10107-003-0448-9.Peer-Reviewed Original ResearchSmoothed Analysis
Spielman D, Teng S. Smoothed Analysis. Lecture Notes In Computer Science 2003, 2748: 256-270. DOI: 10.1007/978-3-540-45078-8_23.Peer-Reviewed Original Research
1997
The complexity of error-correcting codes
Spielman D. The complexity of error-correcting codes. Lecture Notes In Computer Science 1997, 1279: 67-84. DOI: 10.1007/bfb0036172.Peer-Reviewed Original Research