Publications (15)
Electric routing and concurrent flow cutting
Jonathan Kelner, Petar Maymounkov
We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new r…
Learning Mixtures of Gaussians Using Diffusion Models
Khashayar Gatmiry, Jonathan Kelner, Holden Lee
We give a new algorithm for learning mixtures of Gaussians (with identity covariance in ) to TV error , with quasi-polynomial ($O(n^{\text{poly\,log}…
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
We prove that with high probability over the choice of a random graph from the ErdÅs-Rényi distribution , the -time degree Sum-of-Squares semidefinite…
Breaking and making quantum money: toward a new quantum cryptographic protocol
Andrew Lutomirski, Scott Aaronson, Edward Farhi +4
Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There…
Sampling with Barriers: Faster Mixing via Lewis Weights
Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by inequalities in endowed with the metric defined by the Hessian of a convex barrie…
Topology Discovery of Sparse Random Graphs With Few Participants
Animashree Anandkumar, Avinatan Hassidim, Jonathan Kelner
We consider the task of topology discovery of sparse random graphs using end-to-end random measurements (e.g., delay) between a subset of nodes, referred to as the participants. Th…
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
It is well-known that the statistical performance of Lasso can suffer significantly when the covariates of interest have strong correlations. In particular, the prediction error of…
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
Jonathan Kelner, Annie Marsden, Vatsal Sharan +3
We provide new gradient-based methods for efficiently solving a broad class of ill-conditioned optimization problems. We consider the problem of minimizing a function $f : \mathbb{…
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, John Peebles +4
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of t…
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…
On the Power of Preconditioning in Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on…
Feature Adaptation for Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaus…
Rounding Sum-of-Squares Relaxations
Boaz Barak, Jonathan Kelner, David Steurer
We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connec…
High-precision Estimation of Random Walks in Small Space
AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh +3
We provide a deterministic -space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within…
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Gaussian Graphical Models (GGMs) have wide-ranging applications in machine learning and the natural and social sciences. In most of the settings in which they are applied, the numb…