836 citations · 912 across the 5 of their papers we have counts for
6 papers
Lower-Stretch Spanning Trees
Michael Elkin, Yuval Emek, Daniel A. Spielman +1
We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).
Smoothed Analysis of Interior-Point Algorithms: Termination
Daniel A. Spielman, Shang-Hua Teng
We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by…
Smoothed analysis of algorithms
Daniel A. Spielman, Shang-Hua Teng
Spielman and Teng introduced the smoothed analysis of algorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could n…
Exponential algorithmic speedup by quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto +3
We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a c…
Parallel Delaunay Refinement: Algorithms and Analyses
Dan A. Spielman, Shang-hua Teng, Alper Ungor
In this paper, we analyze the complexity of natural parallelizations of Delaunay refinement methods for mesh generation. The parallelizations employ a simple strategy: at each iter…
An Infinite Antichain of Permutations
Miklós Bóna, Daniel A. Spielman
We constructively prove that the partially ordered set of finite permutations ordered by deletion of entries contains an infinite antichain.