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 resourcesThese 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.
|