papers
Publications (7)
cs.CC2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
cs.DS2016
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, John Peebles +4
quant-ph2009
Breaking and making quantum money: toward a new quantum cryptographic protocol
Andrew Lutomirski, Scott Aaronson, Edward Farhi +4
cs.DS2018
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
cs.SI2012
Topology Discovery of Sparse Random Graphs With Few Participants
Animashree Anandkumar, Avinatan Hassidim, Jonathan Kelner
cs.DS2013
Rounding Sum-of-Squares Relaxations
Boaz Barak, Jonathan Kelner, David Steurer
cs.DM2009
Electric routing and concurrent flow cutting
Jonathan Kelner, Petar Maymounkov