Algorithms
Software-defined batteries
Hardness of Approximation Between P and NP
The first question we computer scientists ask when facing a new algorithmic challenge is: is it NP-hard, or is it in P? Surprisingly, for many important problems, the answer is “neither!” I will discuss recent…
Upper bounds on Fourier entropy
The Bullet Problem With Discrete Speeds
Bullets are fired along the real line each second with independent uniformly random speeds from [0,1]. When two bullets collide they mutually annihilate. The still open bullet problem asks if the first bullet is never…
Social Research in the Age of Big Data
The digital age has transformed how researchers are able to study social behavior. These new opportunities mean that the future of social research will involve blending together insights from two communities: social scientists and data…
Matrix Completion has No Spurious Local Minimum
Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various…
