Mathematics
The systematic normal form of lattices, and their algorithmic applications. [joint work with Peter Shor; Lior Eldar]
The systematic normal form of lattices is a new echelon form of lattices in which the entries obey a certain co-primality condition. These lattices can be used to approximate efficiently any lattice, and hence are…
Verifiable Functional Encryption
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…
A smooth transition from Wishart to GOE
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…
Northwest Probability Seminar – Session 3
The local max-cut problem asks to find a partition of the vertices in a weighted graph such that the cut weight cannot be improved by moving a single vertex (that is the partition is locally…
