| 2025 | COLT | Learning Mixtures of Gaussians Using Diffusion Models. | Khashayar Gatmiry, Jonathan A. Kelner, Holden Lee |
| 2024 | COLT | Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier. | Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala |
| 2024 | COLT | Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. | Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi |
| 2023 | COLT | Semi-Random Sparse Recovery in Nearly-Linear Time. | Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian |
| 2023 | FOCS | Matrix Completion in Almost-Verification Time. | Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian |
| 2022 | COLT | Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. | Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan |
| 2022 | ICLR | Optimization and Adaptive Generalization of Three layer Neural Networks. | Khashayar Gatmiry, Stefanie Jegelka, Jonathan A. Kelner |
| 2021 | FOCS | On the Power of Preconditioning in Sparse Linear Regression. | Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi |
| 2020 | FOCS | High-precision Estimation of Random Walks in Small Space. | AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan |
| 2018 | FOCS | Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. | Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford |
| 2017 | STOC | Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. | Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu |
| 2016 | FOCS | A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. | Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin |
| 2016 | FOCS | Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. | Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu |
| 2015 | STOC | Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. | Boaz Barak, Jonathan A. Kelner, David Steurer |
| 2014 | SODA | An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. | Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford |
| 2014 | STOC | Rounding sum-of-squares relaxations. | Boaz Barak, Jonathan A. Kelner, David Steurer |
| 2013 | STOC | A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. | Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu |
| 2012 | POPL | Randomized accuracy-aware program transformations for efficient approximate computations. | Zeyuan Allen Zhu, Sasa Misailovic, Jonathan A. Kelner, Martin C. Rinard |
| 2012 | STOC | Hypercontractivity, sum-of-squares proofs, and their applications. | Boaz Barak, Fernando G. S. L. Brando, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou |
| 2012 | STOC | Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. | Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov |
| 2012 | STOC | Faster approximate multicommodity flow using quadratically coupled flows. | Jonathan A. Kelner, Gary L. Miller, Richard Peng |
| 2011 | STOC | Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. | Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng |
| 2011 | STACS | Spectral Sparsification in the Semi-Streaming Setting. | Jonathan A. Kelner, Alex Levin |
| 2011 | SIGMETRICS | Topology discovery of sparse random graphs with few participants. | Animashree Anandkumar, Avinatan Hassidim, Jonathan A. Kelner |
| 2009 | FOCS | Local Graph Partitions for Approximation and Testing. | Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak |
| 2009 | FOCS | Higher Eigenvalues of Graphs. | Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng |
| 2009 | FOCS | Faster Generation of Random Spanning Trees. | Jonathan A. Kelner, Aleksander Madry |
| 2009 | ICML | Fitting a graph to vector data. | Samuel I. Daitch, Jonathan A. Kelner, Daniel A. Spielman |
| 2009 | ISAAC | Electric Routing and Concurrent Flow Cutting. | Jonathan A. Kelner, Petar Maymounkov |
| 2007 | FOCS | On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. | Jonathan A. Kelner, Evdokia Nikolova |
| 2006 | ESA | Stochastic Shortest Paths Via Quasi-convex Maximization. | Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, Michael Mitzenmacher |
| 2006 | STOC | A randomized polynomial-time simplex algorithm for linear programming. | Jonathan A. Kelner, Daniel A. Spielman |
| 2004 | STOC | Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. | Jonathan A. Kelner |
| 2000 | DCC | Multiple Description Lattice Vector Quantization: Variations and Extensions. | Jonathan A. Kelner, Vivek K. Goyal, Jelena Kovacevic |