Jonathan A. Kelner

78 papers A* 34A 3B 2Journal 38

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