Sotabase

Career

· Professor of Applied Mathematics, MIT Department of Mathematics and CSAIL2007–
· Member, Institute for Advanced Study2006–2007
· PhD in Computer Science, MIT2006–
· B.A. in Mathematics, Harvard University2002–

Publications (142)

Quantized Frame Expansions with Erasures
2001
560
cited
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Symposium on the Theory of Computing · 2010
370
cited
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
ACM-SIAM Symposium on Discrete Algorithms · 2013
280
cited
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
Symposium on the Theory of Computing · 2013
278
cited
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
IEEE Annual Symposium on Foundations of Computer Science · 2016
266
cited
Hypercontractivity, sum-of-squares proofs, and their applications
Symposium on the Theory of Computing · 2012
214
cited
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Symposium on the Theory of Computing · 2014
195
cited
Large-scale identification of genetic design strategies using local search
Molecular Systems Biology · 2009
167
cited
Stochastic Shortest Paths Via Quasi-convex Maximization
Embedded Systems and Applications · 2006
157
cited
Local Graph Partitions for Approximation and Testing
2009 50th Annual IEEE Symposium on Foundations of Computer Science · 2009
139
cited
Fitting a graph to vector data
International Conference on Machine Learning · 2009
130
cited
Rounding sum-of-squares relaxations
Electron. Colloquium Comput. Complex. · 2013
129
cited
Faster Generation of Random Spanning Trees
2009 50th Annual IEEE Symposium on Foundations of Computer Science · 2009
114
cited
Spectral Sparsification in the Semi-streaming Setting
Theory of Computing Systems · 2012
106
cited
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
Symposium on the Theory of Computing · 2016
104
cited
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs , and its Multicommodity Generalizations
2013
99
cited
A randomized polynomial-time simplex algorithm for linear programming
Symposium on the Theory of Computing · 2006
95
cited
Randomized accuracy-aware program transformations for efficient approximate computations
ACM-SIGACT Symposium on Principles of Programming Languages · 2012
92
cited
Multiple description vector quantization with a coarse lattice
IEEE Transactions on Information Theory · 2002
86
cited
Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance
Symposium on the Theory of Computing · 2011
85
cited
Sotabase
Jonathan Kelner | Researcher Profile | Sotabase | Sotabase