Sotabase

Career

· Professor, MIT2017–
· Assistant Professor, Stanford University2013–2016
· Research Assistant, Stanford University2011–2013
· Assistant Research Engineer, UC Berkeley2011–2013
· Postdoctoral Researcher, UC Berkeley2009–2011
· PhD in Computer Science, Carnegie Mellon University2008–
· Postdoctoral Scholar / Member, Institute for Advanced Study2008–2009
· B.S. in Mathematics and Engineering and Applied Science, California Institute of Technology2003–

Publications (236)

Multiplying matrices faster than coppersmith-winograd
Symposium on the Theory of Computing · 2012
1,038
cited
A Refined Laser Method and Faster Matrix Multiplication
ACM-SIAM Symposium on Discrete Algorithms · 2020
509
cited
Subcubic Equivalences between Path, Matrix and Triangle Problems
IEEE Annual Symposium on Foundations of Computer Science · 2010
467
cited
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
IEEE Annual Symposium on Foundations of Computer Science · 2014
399
cited
Fast approximation algorithms for the diameter and radius of sparse graphs
Symposium on the Theory of Computing · 2013
279
cited
Tight Hardness Results for LCS and Other Sequence Similarity Measures
IEEE Annual Symposium on Foundations of Computer Science · 2015
254
cited
ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
International Congress of Mathematicans · 2019
249
cited
Finding, minimizing, and counting weighted subgraphs
Symposium on the Theory of Computing · 2009
214
cited
New Bounds for Matrix Multiplication: from Alpha to Omega
ACM-SIAM Symposium on Discrete Algorithms · 2023
196
cited
Consequences of Faster Alignment of Sequences
International Colloquium on Automata, Languages and Programming · 2014
163
cited
Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
International Symposium on Parameterized and Exact Computation · 2015
153
cited
If the Current Clique Algorithms are Optimal, So is Valiant's Parser
IEEE Annual Symposium on Foundations of Computer Science · 2015
128
cited
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
Symposium on the Theory of Computing · 2015
125
cited
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Symposium on the Theory of Computing · 2015
124
cited
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
ACM-SIAM Symposium on Discrete Algorithms · 2017
123
cited
Better Approximation Algorithms for the Graph Diameter
ACM-SIAM Symposium on Discrete Algorithms · 2014
121
cited
More Asymmetry Yields Faster Matrix Multiplication
ACM-SIAM Symposium on Discrete Algorithms · 2024
90
cited
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
arXiv.org · 2015
85
cited
Listing Triangles
International Colloquium on Automata, Languages and Programming · 2014
81
cited
Finding Four-Node Subgraphs in Triangle Time
ACM-SIAM Symposium on Discrete Algorithms · 2015
79
cited
Sotabase