Jonathan A. Kelner

According to our database, Jonathan A. Kelner authored at least 44 papers between 2000 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

CoRR, 2024

2023

Sampling with Barriers: Faster Mixing via Lewis Weights.

Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala

CoRR, 2023

Feature Adaptation for Sparse Linear Regression.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Matrix Completion in Almost-Verification Time.

Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Semi-Random Sparse Recovery in Nearly-Linear Time.

Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

CoRR, 2022

Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Optimization and Adaptive Generalization of Three layer Neural Networks.

Khashayar Gatmiry, Stefanie Jegelka, Jonathan A. Kelner

Proceedings of the Tenth International Conference on Learning Representations, 2022

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

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

On the Power of Preconditioning in Sparse Linear Regression.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

High-precision Estimation of Random Walks in Small Space.

AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2018

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

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Rumor Spreading with No Dependence on Conductance.

Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov

SIAM J. Comput., 2017

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

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

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

Electron. Colloquium Comput. Complex., 2016

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

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.

Boaz Barak, Jonathan A. Kelner, David Steurer

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

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

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Topology discovery of sparse random graphs with few participants.

Animashree Anandkumar, Avinatan Hassidim, Jonathan A. Kelner

Random Struct. Algorithms, 2013

Spectral Sparsification in the Semi-streaming Setting.

Jonathan A. Kelner, Alex Levin

Theory Comput. Syst., 2013

Rounding Sum-of-Squares Relaxations.

Boaz Barak, Jonathan A. Kelner, David Steurer

Electron. Colloquium Comput. Complex., 2013

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Quantum money.

Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan A. Kelner, Andrew Lutomirski

Commun. ACM, 2012

Faster approximate multicommodity flow using quadratically coupled flows.

Jonathan A. Kelner, Gary L. Miller, Richard Peng

Proceedings of the 44th Symposium on Theory of Computing Conference, 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

Proceedings of the 44th Symposium on Theory of Computing Conference, 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

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Randomized accuracy-aware program transformations for efficient approximate computations.

Zeyuan Allen Zhu, Sasa Misailovic, Jonathan A. Kelner, Martin C. Rinard

Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2012

2011

Electric routing and concurrent flow cutting.

Jonathan A. Kelner, Petar Maymounkov

Theor. Comput. Sci., 2011

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

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Metric uniformization and spectral bounds for graphs

Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng

CoRR, 2010

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

Proceedings of the Innovations in Computer Science, 2010

2009

Fitting a graph to vector data.

Samuel I. Daitch, Jonathan A. Kelner, Daniel A. Spielman

Proceedings of the 26th Annual International Conference on Machine Learning, 2009

Faster Generation of Random Spanning Trees.

Jonathan A. Kelner, Aleksander Madry

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Higher Eigenvalues of Graphs.

Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Local Graph Partitions for Approximation and Testing.

Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2007

On the Hardness and Smoothed Complexity of Quasi-Concave Minimization.

Jonathan A. Kelner, Evdokia Nikolova

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

New geometric techniques for linear programming and graph partitioning.

Jonathan A. Kelner

PhD thesis, 2006

Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus.

Jonathan A. Kelner

SIAM J. Comput., 2006

A randomized polynomial-time simplex algorithm for linear programming.

Jonathan A. Kelner, Daniel A. Spielman

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Stochastic Shortest Paths Via Quasi-convex Maximization.

Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, Michael Mitzenmacher

Proceedings of the Algorithms, 2006

2005

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

Jonathan A. Kelner, Daniel A. Spielman

Electron. Colloquium Comput. Complex., 2005

2002

Multiple description vector quantization with a coarse lattice.

Vivek K. Goyal, Jonathan A. Kelner, Jelena Kovacevic

IEEE Trans. Inf. Theory, 2002

2000

Multiple Description Lattice Vector Quantization: Variations and Extensions.

Jonathan A. Kelner, Vivek K. Goyal, Jelena Kovacevic

Proceedings of the Data Compression Conference, 2000