Important Dates >
DS-GA 3001 Special Topics in Data Science: MATHEMATICS OF DATA SCIENCE: Graphs and Networks
(Spring 2018, NYU Center for Data Science)
Afonso S. Bandeira
Lectures: Thu 4.55pm-6.35pm at CDS110 (60 5th Av).
Section Leader: Shuyang Ling
Lab section: Wed 7.45pm-8.35pm at CDS110
Office Hours Afonso: Thu 6.35pm-7.35pm at CDS603 or CDS110 (or by appointment at CIWW1123)
Office Hours Shuyang: Wed 4.30pm-5:30pm at CIWW 1103
Piazza page: https://piazza.com/nyu/spring2018/dsga3001/home
(sign up for announcements! Piazza is also ideal to ask questions!)
Graders: Chen Li and Luca Venturi (you can contact them on Piazza, or by email)
Events of potential interest: The Math and Data seminar meets on Thursday before the class, you can see the schedule here and sign up for the mailing list here. Also, I organize weekly (on Wednesday) group meetings and reading groups on several topics related to Math and Data. If you are interested in research in this area you are more than welcome to join (at whatever frequency you want). You can see the schedule and more information here, and sign up for the mailing list here.
Prerequisites: Working knowledge of linear algebra and basic probability is required. Some familiarity with the basics of optimization and algorithms is also recommended.
Syllabus: This is part of a two course series on Mathematics of Data Science. Each part can be taken independently, and they can be taken in any order, the other part can be found here. This part focus on algorithms on graphs and networks while the other in high dimensional data. This is a mostly self-contained research-oriented and fast-paced course designed for graduate students with an interest in doing research in theoretical aspects of algorithms that aim to extract information from data. These often lie in overlaps of (Applied) Mathematics with: Computer Science, Electrical Engineering, Statistics, Operations Research and/or Statistical Physics. Each lecture will feature a couple of Mathematical Open Problem(s) with relevance in Data Science. The main mathematical tools used will be Probability and Linear Algebra, and a working knowledge of these subjects is required. There will also be some (although knowledge of these tools is not assumed) Graph Theory, Representation Theory, Applied Harmonic Analysis, among others. The topics treated will include Random Matrices, Approximation Algorithms, Convex Relaxations, Community detection in graphs, and several others.
The Syllabus includes: Matrix Concentration, Approximation Algorithms and Max-Cut, Community Detection and the Stochastic Block Model, Synchronization Problems and Alignment, Cheeger's Inequality, Semidefinite Programming relaxations, Approximate Message Passing algorithms, and (if time permits) statistical physics heuristics for computational limits of problem on networks.
Please email the instructor at email@example.com if you have any question.
Open problems will be presented at the end of most lectures.
Some of the open problems will also be posted in my blog.
I am here to help: please let me know of your goals for your project and keep me up to date of your progress on it. If you have any question, want to discuss a problem, or brainstorm about any research idea, just email me and we'll schedule a time to meet.
Feedback: Also, if you have any comment or feedback on the class (it's going too fast, too slow, you want me to cover more of something, or less of something else, etc) please let me know (in person or through email) or submit a comment to this google form. Having direct feedback from you is the best way for me to try give lectures that you like! (keep in mind that I don't know who sent me the comment or feedback and there is no way for me to answer, for questions use email, Piazza, or my blog).
Lecture Notes and Extended Syllabi: