JK
Jonathan A. Kelner
cs.DScs.LGstat.MLmath.STstat.THcs.CCcs.DMcs.NAmath.NAmath.OC
On Valency
published · living versionsW_d9p2aje4·v1 · currentpublished
Transformers Learn Two Competing Sorting Algorithms, and Only One Length-Generalizes
with Khashayar Gatmiry, Nathan W. Henry, Chloe H. Su, Emmanuel Abbe +3
1 version
Preprints & journals
31 papers in the corpus · 2009–2026Transformers Learn Two Competing Sorting Algorithms, and Only One Length-Generalizes2610.26974v1 · Khashayar Gatmiry, Nathan W. Henry, Chloe H. Su et al.2026 · 0 citationsarXivon Valency
Solving Linear Systems in Bit Operations2609.38101v1 · Jonathan A. Kelner2026 · 0 citationsarXiv
Learning Mixtures of Gaussians Using Diffusion Models2404.18869v2 · Khashayar Gatmiry, Jonathan Kelner, Holden Lee2024 · 1 citationarXiv
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps2402.15409v1 · Jonathan Kelner, Frederic Koehler, Raghu Meka et al.2024 · 0 citationsarXiv
Matrix Completion in Almost-Verification Time2308.03661v1 · Jonathan A. Kelner, Jerry Li, Allen Liu et al.2023 · 0 citationsarXiv
Feature Adaptation for Sparse Linear Regression2305.16892v1 · Jonathan Kelner, Frederic Koehler, Raghu Meka et al.2023 · 1 citationarXiv
Sampling with Barriers: Faster Mixing via Lewis Weights2303.00480v2 · Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala2023 · 0 citationsarXiv
Semi-Random Sparse Recovery in Nearly-Linear Time2203.04002v1 · Jonathan A. Kelner, Jerry Li, Allen Liu et al.2022 · 1 citationarXiv
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs2203.02824v1 · Jonathan A. Kelner, Frederic Koehler, Raghu Meka et al.2022 · 0 citationsarXiv
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales2111.03137v1 · Jonathan Kelner, Annie Marsden, Vatsal Sharan et al.2021 · 0 citationsarXiv
On the Power of Preconditioning in Sparse Linear Regression2106.09207v1 · Jonathan Kelner, Frederic Koehler, Raghu Meka et al.2021 · 3 citationsarXiv
High-precision Estimation of Random Walks in Small Space1912.04524v3 · AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh et al.2019 · 20 citationsarXiv
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds1905.01282v3 · Jonathan Kelner, Frederic Koehler, Raghu Meka et al.2019 · 5 citationsarXiv
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations1811.10722v1 · Michael B. Cohen, Jonathan Kelner, Rasmus Kyng et al.2018 · 37 citationsarXiv
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs1611.00755v1 · Michael B. Cohen, Jonathan Kelner, John Peebles et al.2016 · 61 citationsarXiv
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More1608.03270v2 · Michael B. Cohen, Jon Kelner, John Peebles et al.2016 · 49 citationsarXiv
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem1604.03084v2 · Boaz Barak, Samuel B. Hopkins, Jonathan Kelner et al.2016 · 165 citationsarXiv
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method1407.1543v2 · Boaz Barak, Jonathan A. Kelner, David Steurer2014 · 129 citationsarXiv
Rounding Sum-of-Squares Relaxations1312.6652v1 · Boaz Barak, Jonathan Kelner, David Steurer2013 · 94 citationsarXiv
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations1304.2338v2 · Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia et al.2013 · 181 citationsarXiv
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time1301.6628v1 · Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford et al.2013 · 196 citationsarXiv
Hypercontractivity, Sum-of-Squares Proofs, and their Applications1205.4484v3 · Boaz Barak, Fernando G.S.L. Brandao, Aram W. Harrow et al.2012 · 194 citationsProc. STOC 2012, pp. 307--326
Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows1202.3367v3 · Jonathan A. Kelner, Gary Miller, Richard Peng2012 · 35 citationsarXiv
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance1104.2944v1 · Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner et al.2011 · 11 citationsarXiv
Topology Discovery of Sparse Random Graphs With Few Participants1102.5063v3 · Animashree Anandkumar, Avinatan Hassidim, Jonathan Kelner2011 · 29 citationsarXiv
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs1010.2921v2 · Paul Christiano, Jonathan A. Kelner, Aleksander Madry et al.2010 · 282 citationsarXiv
Metric uniformization and spectral bounds for graphs1008.3594v3 · Jonathan A. Kelner, James R. Lee, Gregory N. Price et al.2010 · 24 citationsarXiv
Breaking and making quantum money: toward a new quantum cryptographic protocol0912.3825v1 · Andrew Lutomirski, Scott Aaronson, Edward Farhi et al.2009 · 46 citationsInnovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 20-31, 978-7-302-21752-7 Tsinghua University Press
Electric routing and concurrent flow cutting0909.2859v1 · Jonathan Kelner, Petar Maymounkov2009 · 10 citationsarXiv
Faster generation of random spanning trees0908.1448v1 · Jonathan A. Kelner, Aleksander Madry2009 · 83 citationsarXiv
Large-scale identification of genetic design strategies using local search.19690565 · Lun, Desmond S, Rockwell, Graham, Guido, Nicholas J et al.2009 · 155 citationsMolecular systems biology. 2009;5:296
Career total: 84 works. 31 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.