Multiple Description Lattice Vector Quantization: Variations and Extensions. - Jonathan A. Kelner; Vivek K. Goyal; Jelena Kovacevic (Data Compression Conference, 2000)

Multiple description vector quantization with a coarse lattice. - Vivek K. Goyal; Jonathan A. Kelner; Jelena Kovacevic (IEEE Trans. Inf. Theory, 2002)

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version) - Jonathan A. Kelner; Daniel A. Spielman (Electron. Colloquium Comput. Complex., 2005)

Stochastic Shortest Paths Via Quasi-convex Maximization. - Evdokia Nikolova; Jonathan A. Kelner; Matthew Brand; Michael Mitzenmacher (ESA, 2006)

A randomized polynomial-time simplex algorithm for linear programming. - Jonathan A. Kelner; Daniel A. Spielman (STOC, 2006)

Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus. - Jonathan A. Kelner (SIAM J. Comput., 2006)

New geometric techniques for linear programming and graph partitioning. - Jonathan A. Kelner (2006)

On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. - Jonathan A. Kelner; Evdokia Nikolova (FOCS, 2007)

Local Graph Partitions for Approximation and Testing. - Avinatan Hassidim; Jonathan A. Kelner; Huy N. Nguyen; Krzysztof Onak (FOCS, 2009)

Higher Eigenvalues of Graphs. - Jonathan A. Kelner; James R. Lee; Gregory N. Price; Shang-Hua Teng (FOCS, 2009)

Faster Generation of Random Spanning Trees. - Jonathan A. Kelner; Aleksander Madry (FOCS, 2009)

Fitting a graph to vector data. - Samuel I. Daitch; Jonathan A. Kelner; Daniel A. Spielman (ICML, 2009)

Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol. - Andrew Lutomirski; Scott Aaronson; Edward Farhi; David Gosset; Jonathan A. Kelner; Avinatan Hassidim; Peter W. Shor (ICS, 2010)

Metric uniformization and spectral bounds for graphs - Jonathan A. Kelner; James R. Lee; Gregory N. Price; Shang-Hua Teng (CoRR, 2010)

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 (STOC, 2011)

Electric routing and concurrent flow cutting. - Jonathan A. Kelner; Petar Maymounkov (Theor. Comput. Sci., 2011)

Randomized accuracy-aware program transformations for efficient approximate computations. - Zeyuan Allen Zhu; Sasa Misailovic; Jonathan A. Kelner; Martin C. Rinard (POPL, 2012)

Hypercontractivity, sum-of-squares proofs, and their applications. - Boaz Barak; Fernando G. S. L. Brandão; Aram W. Harrow; Jonathan A. Kelner; David Steurer; Yuan Zhou 007 (STOC, 2012)

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 (STOC, 2012)

Faster approximate multicommodity flow using quadratically coupled flows. - Jonathan A. Kelner; Gary L. Miller; Richard Peng (STOC, 2012)

Quantum money. - Scott Aaronson; Edward Farhi; David Gosset; Avinatan Hassidim; Jonathan A. Kelner; Andrew Lutomirski (Commun. ACM, 2012)

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. - Jonathan A. Kelner; Lorenzo Orecchia; Aaron Sidford; Zeyuan Allen Zhu (STOC, 2013)

Rounding Sum-of-Squares Relaxations. - Boaz Barak; Jonathan A. Kelner; David Steurer (Electron. Colloquium Comput. Complex., 2013)

Spectral Sparsification in the Semi-streaming Setting. - Jonathan A. Kelner; Alex Levin (Theory Comput. Syst., 2013)

Topology discovery of sparse random graphs with few participants. - Animashree Anandkumar; Avinatan Hassidim; Jonathan A. Kelner (Random Struct. Algorithms, 2013)

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 (SODA, 2014)

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. - Boaz Barak; Jonathan A. Kelner; David Steurer (STOC, 2015)

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 (FOCS, 2016)

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 (STOC, 2017)

Rumor Spreading with No Dependence on Conductance. - Keren Censor-Hillel; Bernhard Haeupler; Jonathan A. Kelner; Petar Maymounkov (SIAM J. Comput., 2017)

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 (FOCS, 2018)

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. - Boaz Barak; Samuel B. Hopkins 001; Jonathan A. Kelner; Pravesh K. Kothari; Ankur Moitra; Aaron Potechin (SIAM J. Comput., 2019)

High-precision Estimation of Random Walks in Small Space. - AmirMahdi Ahmadinejad; Jonathan A. Kelner; Jack Murtagh; John Peebles; Aaron Sidford; Salil P. Vadhan (FOCS, 2020)

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Ankur Moitra (NeurIPS, 2020)

On the Power of Preconditioning in Sparse Linear Regression. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (FOCS, 2021)

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 (COLT, 2022)

Optimization and Adaptive Generalization of Three layer Neural Networks. - Khashayar Gatmiry; Stefanie Jegelka; Jonathan A. Kelner (ICLR, 2022)

Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (NeurIPS, 2022)

Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (CoRR, 2022)

Semi-Random Sparse Recovery in Nearly-Linear Time. - Jonathan A. Kelner; Jerry Li 001; Allen Liu; Aaron Sidford; Kevin Tian (COLT, 2023)

Matrix Completion in Almost-Verification Time. - Jonathan A. Kelner; Jerry Li 001; Allen Liu; Aaron Sidford; Kevin Tian (FOCS, 2023)

Feature Adaptation for Sparse Linear Regression. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (NeurIPS, 2023)

Sampling with Barriers: Faster Mixing via Lewis Weights. - Khashayar Gatmiry; Jonathan A. Kelner; Santosh S. Vempala (CoRR, 2023)

Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier. - Khashayar Gatmiry; Jonathan A. Kelner; Santosh S. Vempala (COLT, 2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (COLT, 2024)

Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting. - Jonathan A. Kelner; Jerry Li 001; Allen Liu; Aaron Sidford; Kevin Tian (NeurIPS, 2024)

Learning Mixtures of Gaussians Using Diffusion Models. - Khashayar Gatmiry; Jonathan A. Kelner; Holden Lee (COLT, 2025)