Jonathan A. Kelner

Publication Activity (10 Years)

Years Active: 2000-2024
Publications (10 Years): 35

Top Venues

CoRR

FOCS

COLT

STOC

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. COLT (2024)
Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala
Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier. COLT (2024)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. CoRR (2024)
Khashayar Gatmiry, Jonathan A. Kelner, Holden Lee
Learning Mixtures of Gaussians Using Diffusion Models. CoRR (2024)
Jonathan A. Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian
Semi-Random Sparse Recovery in Nearly-Linear Time. COLT (2023)
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
Matrix Completion in Almost-Verification Time. CoRR (2023)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Feature Adaptation for Sparse Linear Regression. NeurIPS (2023)
Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala
Sampling with Barriers: Faster Mixing via Lewis Weights. CoRR (2023)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Feature Adaptation for Sparse Linear Regression. CoRR (2023)
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
Matrix Completion in Almost-Verification Time. FOCS (2023)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs. NeurIPS (2022)
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. COLT (2022)
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
Semi-Random Sparse Recovery in Nearly-Linear Time. CoRR (2022)
Khashayar Gatmiry, Stefanie Jegelka, Jonathan A. Kelner
Optimization and Adaptive Generalization of Three layer Neural Networks. ICLR (2022)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs. CoRR (2022)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
On the Power of Preconditioning in Sparse Linear Regression. FOCS (2022)
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. CoRR (2021)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
On the Power of Preconditioning in Sparse Linear Regression. CoRR (2021)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
On the Power of Preconditioning in Sparse Linear Regression. FOCS (2021)
AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan
High-precision Estimation of Random Walks in Small Space. FOCS (2020)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. NeurIPS (2020)
AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan
High-precision Estimation of Random Walks in Small Space. CoRR (2019)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. 48 (2) (2019)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. CoRR (2019)
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. FOCS (2018)
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. CoRR (2018)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. STOC (2017)
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
Rumor Spreading with No Dependence on Conductance. SIAM J. Comput. 46 (1) (2017)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. 23 (2016)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. CoRR (2016)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. CoRR (2016)
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. FOCS (2016)
Boaz Barak, Jonathan A. Kelner, David Steurer
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. STOC (2015)
Boaz Barak, Jonathan A. Kelner, David Steurer
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. CoRR (2014)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding sum-of-squares relaxations. STOC (2014)
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. SODA (2014)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding Sum-of-Squares Relaxations. CoRR (2013)
Jonathan A. Kelner, Alex Levin
Spectral Sparsification in the Semi-streaming Setting. Theory Comput. Syst. 53 (2) (2013)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding Sum-of-Squares Relaxations. Electron. Colloquium Comput. Complex. 20 (2013)
Jonathan A. Kelner, Lorenzo Orecchia, Yin Tat Lee, Aaron Sidford
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations CoRR (2013)
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. STOC (2013)
Animashree Anandkumar, Avinatan Hassidim, Jonathan A. Kelner
Topology discovery of sparse random graphs with few participants. Random Struct. Algorithms 43 (1) (2013)
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time CoRR (2013)
Jonathan A. Kelner, Gary L. Miller, Richard Peng
Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows. CoRR (2012)
Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan A. Kelner, Andrew Lutomirski
Quantum money. Commun. ACM 55 (8) (2012)
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
Hypercontractivity, sum-of-squares proofs, and their applications. STOC (2012)
Zeyuan Allen Zhu, Sasa Misailovic, Jonathan A. Kelner, Martin C. Rinard
Randomized accuracy-aware program transformations for efficient approximate computations. POPL (2012)
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
Hypercontractivity, Sum-of-Squares Proofs, and their Applications CoRR (2012)
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. STOC (2012)
Jonathan A. Kelner, Gary L. Miller, Richard Peng
Faster approximate multicommodity flow using quadratically coupled flows. STOC (2012)
Jonathan A. Kelner, Petar Maymounkov
Electric routing and concurrent flow cutting. Theor. Comput. Sci. 412 (32) (2011)
Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. STOC (2011)
Animashree Anandkumar, Avinatan Hassidim, Jonathan A. Kelner
Topology Discovery of Sparse Random Graphs With Few Participants CoRR (2011)
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance CoRR (2011)
Animashree Anandkumar, Avinatan Hassidim, Jonathan A. Kelner
Topology discovery of sparse random graphs with few participants. SIGMETRICS (2011)
Jonathan A. Kelner, Alex Levin
Spectral Sparsification in the Semi-Streaming Setting. STACS (2011)
Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng
Metric uniformization and spectral bounds for graphs CoRR (2010)
Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs CoRR (2010)
Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, Peter W. Shor
Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol. ICS (2010)
Samuel I. Daitch, Jonathan A. Kelner, Daniel A. Spielman
Fitting a graph to vector data. ICML (2009)
Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak
Local Graph Partitions for Approximation and Testing. FOCS (2009)
Jonathan A. Kelner, Aleksander Madry
Faster generation of random spanning trees CoRR (2009)
Jonathan A. Kelner, Aleksander Madry
Faster Generation of Random Spanning Trees. FOCS (2009)
Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng
Higher Eigenvalues of Graphs. FOCS (2009)
Jonathan A. Kelner, Petar Maymounkov
Electric Routing and Concurrent Flow Cutting. ISAAC (2009)
Jonathan A. Kelner, Petar Maymounkov
Electric routing and concurrent flow cutting CoRR (2009)
Jonathan A. Kelner, Evdokia Nikolova
On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. FOCS (2007)
Jonathan A. Kelner
Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus. SIAM J. Comput. 35 (4) (2006)
Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, Michael Mitzenmacher
Stochastic Shortest Paths Via Quasi-convex Maximization. ESA (2006)
Jonathan A. Kelner, Daniel A. Spielman
A randomized polynomial-time simplex algorithm for linear programming. STOC (2006)
Jonathan A. Kelner, Daniel A. Spielman
A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version) Electron. Colloquium Comput. Complex. (156) (2005)
Jonathan A. Kelner
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. STOC (2004)
Vivek K. Goyal, Jonathan A. Kelner, Jelena Kovacevic
Multiple description vector quantization with a coarse lattice. IEEE Trans. Inf. Theory 48 (3) (2002)
Jonathan A. Kelner, Vivek K. Goyal, Jelena Kovacevic
Multiple Description Lattice Vector Quantization: Variations and Extensions. Data Compression Conference (2000)

Jonathan A. Kelner.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jonathan A. Kelner