Mathematics of Data Science course at NYU Courant

I am teaching a Mathematics of Data Science PhD level course at NYU Courant this Fall, I’ll be posting new Open Problems in this blog! See more info here.

SDP for Community Detection with many communities

I am happy to announce that there is significant progress on Open Problem 9.2. of my notes, in this paper Bruce Hajek, Yihong Wu, and Jiaming Xu show that, indeed, for communities, the natural Semidefinite Program is suboptimal!

Congratulations to the three!

 

Generalized Power Method for SO(2) Synchronization

More great news, this time about Open Problem 10.1. of Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science: Nicolas Boumal (who has contributed to this blog!) has made significant progress on this problem on his new paper.

Below the Kesten-Stigum bound for Community Detection

I have great news: There was (a lot) of progress on the Open Problem 9.1. of Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science in the last couple of weeks, independently by Emmanuel Abbe & Colin Sandon and by Jess Banks & Cristopher Moore.

Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science

The lecture notes for the course I gave this semester are now available here. Thanks to all the readers that gave me comments and feedback on the notes! I am sure the notes still contain many typos, if you find one, or have any general feedback, please let me know!

Courant Institute of Mathematical Sciences

Finally, I am no longer in the job market! I am excited to announce that I will join the Courant Institute of Mathematical Sciences as an Assistant Professor in the Department of Mathematics with a joint appointment in the Center for Data Science!

I will join Courant in the Summer of 2016, until then I am spending a year in the Department of Mathematics at MIT as an Instructor of Applied Mathematics.

Warm thanks to all the other departments that hosted me this Spring and all of the people that helped me enjoy each and every visit, rendering my final decision extremely difficult! I had an amazing time, albeit completely exhausting.

The 4M-4 conjecture is false!

Cynthia Vinzant just disproved part (a) of the  conjecture, see here!

We posed the  conjecture two years ago, and there was even a monetary motivation for it! I will not go into details regarding the conjecture, you can read more about it either on a previous blog post of mine or a post of Dustin Mixon. In a nutshell it tries to predict how many phaseless measurements are needed to identify a complex vector of dimensions. The conjecture was that (a)  measurements are always needed and (b)  measurements suffice (as long as sufficiently generic).

Tightness of the Angular Synchronization SDP relaxation and rank recovery

A few weeks ago, Nicolas, Amit, and myself uploaded our new paper entitled “Tightness of the maximum likelihood semidefinite relaxation for angular synchronization”. I am quite excited about this one as it is the first instance for which we were able to establish a rank recovery type of result! I will briefly explain the main result, its motivation, and describe some of the main ideas behind the proof.

Lecture on Semidefinite Relaxation for Community Detection

Later today I am giving a lecture in IMPA, Brazil . It is part of a special course on Randomness, Matrices and High Dimensional Problems (given together with Roberto Oliveira). Below are the notes for today’s lecture. See here for a printer friendly version. The content is based on a result in here.

1. The problem we will focus on

Let be an even positive integer. Given two sets of nodes consider the following random graph : For each pair of nodes, is an edge of with probability if and are in the same set and if they are in different sets. Each edge is drawn independently and .

(Think nodes as fans of Fluminense and Flamengo and edges representing friendships, in this model, fans of the same club are more likely to be friends)

For which values of and can we recover the partition, with an efficient algorithm, from only looking at the graph (with high probability)?

Conditional Restricted Isometries

We have finally made (conditional) progress on the Paley ETF conjecture! Joel, Dustin, and I just uploaded our paper “A conditional construction of restricted isometries” to the arxiv. The conjecture states that a particularly simple deterministic construction, the Paley ETF (see below), satisfies the restricted isometry property past the squareroot bottleneck, we were able to establish this conditional on a folklore number theory conjecture.