Mathematics
Publication
Outlaw distributions and locally decodable codes
Publication
Lipschitz Percolation
Video
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…
Publication
Verifiable Functional Encryption
Video
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…
Publication
Upper bounds on Fourier entropy
Video
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…
Publication