CS 496: Learning in Networks, Fall 2023

Basic info

Course description: This is a graduate topics course on learning in networks, focusing in particular on fundamental statistical and computational limits. Topics include the planted clique problem, community detection, high-dimensional random geometric graphs, root-finding algorithms, graph matching, information-computation gaps, and more. While exploring these topics, we will discuss several general techniques that are applicable more broadly, such as the first and second moment methods, concentration inequalities, martingales, branching processes, information-theoretic methods, spectral algorithms, and more.

Goals: The goals of the course are three-fold: (1) to give an overview of recent research progress in the area; (2) to highlight ideas and techniques that are broadly useful, enriching students' technical tool box; and (3) to highlight open problems and create excitement about future research in the area.

Prerequisites: General mathematical maturity. More specifically, familiarity with probability, linear algebra, statistics, and algorithms. Please contact the instructor with questions.

Instructor: Miklos Z. Racz
Lecture time and location: MW 11:00 am - 12:20 pm, Tech LG66
Office hours: M 2 - 4 pm, 2006 Sheridan Rd, Room 108

Grading and course policies

Grading: The course grade will be based on the following breakdown:
Homework: There will be 2-3 problem sets throughout the quarter.

Paper presentation: Every student will pick a recent research paper and prepare a 20 minute presentation on it. The last couple of weeks of the course will be devoted to student presentations. A large list of possible papers will be provided before the start of the course.


The course will combine material from a number of recent lecture notes and surveys, as well as recent research papers. These include (all freely available online):

Back to Teaching Home