Fetching the paper…
Reading the bibliography…
In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input.
The Simplex Method: a probabilistic analysis
K. H. Borgwardt · 1980
Earlier work this paper cites.
Amortized efficiency of list update and paging rules
D. D. Sleator and R. E. Tarjan · 1985
Earlier work this paper cites.
Large cliques elude the Metropolis process
M. Jerrum · 1992
Earlier work this paper cites.
Coloring random and semi-random
A. Blum and J. H. Spencer · 1995
Earlier work this paper cites.
Finding a large hidden clique in a random graph
N. Alon, M. Krivelevich, and B. Sudakov · 1998
Earlier work this paper cites.
Latent semantic indexing: A probabilistic analysis
C. H. Papadimitriou, P. Raghgavan, H. Tamaki, and S. Vemapala · 2000
Earlier work this paper cites.
Heuristics for semirandom graph problems
U. Feige and J. Kilian · 2001
Earlier work this paper cites.
Optimal aggregation algorithms for middleware
R. Fagin, A. Lotem, and M. Naor · 2003
Earlier work this paper cites.
Smoothed analysis: Why the simplex algorithm usually takes polynomial time
D. A. Spielman and S.-H. Teng · 2004
Earlier work this paper cites.
On paging with locality of reference
S. Albers, L. M. Favrholdt, and O. Giel · 2005
Earlier work this paper cites.
Robust uncertainty principles: Exact signal reconstruction from highly incomplete fourier information
E. J. Candes, J. K. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Compressed sensing
D. L. Donoho · 2006
Earlier work this paper cites.
Clusterability: A theoretical study
M. Ackerman and S. Ben-David · 2009
Earlier work this paper cites.
Clustering with spectral norm and the
A. Kumar and R. Kannan · 2010
Earlier work this paper cites.
Smoothed analysis of the k-means method
D. Arthur, B. Manthey, and H. Röglin · 2011
Cited alongside, same era.
Settling the complexity of local max-cut (almost) completely
R. Elsässer and T. Tscheuschner · 2011
Cited alongside, same era.
Center-based clustering under perturbation stability
P. Awasthi, A. Blum, and O. Sheffet · 2012
Cited alongside, same era.
Are stable instances easy?
Y. Bilu and N. Linial · 2012
Cited alongside, same era.
Clustering is difficult only when it does not matter
A. Daniely, N. Linial, and M. Saks · 2012
Cited alongside, same era.
The effectiveness of Lloyd-type methods for the k-means problem
R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy · 2012
Cited alongside, same era.
Deep Learning
I. Goodfellow, Y. Bengio, and A. Courville · 2016
Later among the works it cites.
How robust are reconstruction thresholds for community detection?
A. Moitra, W. Perry, and A. S. Wein · 2016
Later among the works it cites.
Local MAX-CUT in smoothed polynomial time
O. Angel, S. Bubeck, Y. Peres, and F. Wai · 2017
Later among the works it cites.
Algorithms for stable and perturbation-resilient problems
H. Angelidakis, K. Makarychev, and Y. Makarychev · 2017
Later among the works it cites.
Being robust (in high dimensions) can be practical
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Later among the works it cites.
Smoothed analysis of local search for the maximum-cut problem
M. Etscheid and H. Röglin · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A practical algorithm for topic modeling with provable guarantees
S. Arora, R. Ge, Y. Halpern, D. M. Mimno, A. Moitra, D. Sontag, Y. Wu, and M. Zhu · 2013
Cited alongside, same era.
Clustering under approximation stability
M.-F. Balcan, A. Blum, and A. Gupta · 2013
Cited alongside, same era.
Bilu-Linial stable instances of max cut and minimum multiway cut
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2014
Cited alongside, same era.
Inapproximability of combinatorial optimization problems
L. Trevisan · 2014
Cited alongside, same era.
Parameterized Algorithms
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh · 2015
Cited alongside, same era.
k-center clustering under perturbation resilience
M.-F. Balcan, N. Haghtalab, and C. White · 2016
Cited alongside, same era.
Application-specific algorithm selection
R. Gupta and T. Roughgarden · 2017
Later among the works it cites.
How to escape saddle points efficiently
C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan · 2017
Later among the works it cites.
The computer science and physics of community detection: Landscapes, phase transitions, and hardness
C. Moore · 2017
Later among the works it cites.
Implicit Regularization in Deep Learning
B. Neyshabur · 2017
Later among the works it cites.
CS264 lecture notes on beyond worst-case analysis
T. Roughgarden · 2017
Later among the works it cites.
Understanding deep learning requires rethinking generalization
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals · 2017
Later among the works it cites.
A friendly smoothed analysis of the simplex method
D. Dadush and S. Huiberts · 2018
Closest in time.