Sotabase

Career

· Professor of Electrical Engineering and Computer Science, Massachusetts Institute of Technology2020–
· Associate Professor (with tenure) of EECS, Massachusetts Institute of Technology2017–2020
· Assistant Professor, Stanford University2011–2016
· Josef Raviv Postdoctoral Fellow, IBM Almaden Research Center2009–2011
· Member (Postdoc) of the School of Mathematics, Institute for Advanced Study2008–2009
· PhD in Computer Science, Carnegie Mellon University2007–
· Postdoctoral Research Fellow, Carnegie Mellon University2007–2008
· Master of Engineering in Computer Science, Cornell University2002–
· Bachelor of Arts in Computer Science and Mathematics with Honors, Cornell University2001–

Publications (210)

On the complexity of optimal K-anonymity
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · 2004
915
cited
A new algorithm for optimal 2-constraint satisfaction and its implications
Theoretical Computer Science · 2005
522
cited
Subcubic Equivalences between Path, Matrix and Triangle Problems
IEEE Annual Symposium on Foundations of Computer Science · 2010
467
cited
Backdoors To Typical Case Complexity
International Joint Conference on Artificial Intelligence · 2003
389
cited
Non-uniform ACC Circuit Lower Bounds
2011 IEEE 26th Annual Conference on Computational Complexity · 2011
307
cited
Faster all-pairs shortest paths via circuit complexity
Symposium on the Theory of Computing · 2013
280
cited
On the possibility of faster SAT algorithms
ACM-SIAM Symposium on Discrete Algorithms · 2010
252
cited
Improving exhaustive search implies superpolynomial lower bounds
Symposium on the Theory of Computing · 2010
222
cited
Finding, minimizing, and counting weighted subgraphs
Symposium on the Theory of Computing · 2009
214
cited
Finding paths of length k in O*(2k) time
Information Processing Letters · 2008
212
cited
Deterministic APSP, Orthogonal Vectors, and More
ACM-SIAM Symposium on Discrete Algorithms · 2016
149
cited
LIMITS and Applications of Group Algebras for Parameterized Problems
ACM Trans. Algorithms · 2009
136
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
Probabilistic Polynomials and Hamming Nearest Neighbors
IEEE Annual Symposium on Foundations of Computer Science · 2015
119
cited
Regularity Lemmas and Combinatorial Algorithms
2009 50th Annual IEEE Symposium on Foundations of Computer Science · 2009
97
cited
New algorithms and lower bounds for circuits with linear threshold gates
Symposium on the Theory of Computing · 2014
91
cited
Polynomial Representations of Threshold Functions and Algorithmic Applications
IEEE Annual Symposium on Foundations of Computer Science · 2016
89
cited
Natural proofs versus derandomization
Symposium on the Theory of Computing · 2012
70
cited
Faster Online Matrix-Vector Multiplication
ACM-SIAM Symposium on Discrete Algorithms · 2016
65
cited
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Symposium on the Theory of Computing · 2015
60
cited
Sotabase