Average-case complexity and statistical inference.
Notes from each lecture will be uploaded after the lecture. The course information is here and includes dates. Generally we meet Wednesday 3.15-5pm in the seminar room in house 6 : Spring 2023.I'll maintain cumulative lecture notes (last updated 24th May). Link to the first exercise sheet is here, and second exercise sheet is here.
■ L1 (Jan 26). Introduction and definition of strong and weak detection. Introduced planted submatrix model. slides and notes
■ L2 (Feb 1). Planted submatrix: easy and possible regimes. Planted clique model: possible regime.
■ L3 (Feb 15). Planted clique: impossible region.
■ L4 (Feb 22). Intro to low degree hardness.
■ L5 (Mar 1). Low degree hardness for planted clique.
■ L6 (Mar 8). Reductions.
■ L7 (Mar 15). Total variation distance.
break
■ L8 (Apr 26). Reduction from planted clique to planted submatrix I.
■ L9 (May 3). Exercises.
■ L10 (May 10). Reduction from planted clique to planted submatrix II.
■ L11 (May 16). Note! Tuesday 1-3pm. Lower bounds from subgraph counts I.
■ L12 (May 24). Lower bounds from subgraph counts II.
■ L13 (May 31). Problem Session.
Possible Reading and other resources
These go beyond the scope of this course.● Yihong Wu and Jiaming Xu's Statistical Inference on Graphs lecture notes.
● Gabor Lugosi's Lectures on Combinatorial Statistics lecture notes.
Tutorial by Guy Bresler on reduction from planted clique to planted submatrix video.
 |