Class | Date | Topic | Slides | Notes | References |
---|---|---|---|---|---|

Part I. Explicit constructions of rigid matrices. | |||||

1 | 08/26 | Introduction and course overview. Definition, examples, and applications of matrix rigidity. | Slides | Notes | [Val77], [Vio09, Sec 3.2] |

2 | 08/31 | Rigidity and circuits, existence of rigid matrices. | Slides | Notes | [Val77], [Vio09, Sec 3.2] |

Homework 1 | |||||

3 | 09/02 | Explicit and non-explicit matrices. | Slides | Notes | [PR94], [RBG01] |

4 | 09/07 | Error correcting codes, Friedman's rigidity lower bound. | Slides | Notes | [Fri93] |

5 | 09/09 | Lower Bounds of Pudlák and Rödl; and Shokrollahi, Spielman, and Stemann. | Slides | Notes | [PR94], [SSS97] |

6 | 09/14 | Rigidity of Hadamard. | Slides | Notes | [dW06], [Lok95] |

7 | 09/16 | Overview of tools used in Part I. | Slides | Notes | |

8 | 09/21 | Overview of tools used in Part I. | Slides | Notes | |

Part II. Semi-explicit constructions of rigid matrices. | |||||

9 | 09/23 | Shoup-Smolensky dimension, rigid matrices with a few algebraically independent entries. | Slides | Notes | [Lok00] |

10 | 09/28 | Rigidity and circuit lower bounds for matrices with linearly independent entries. | Slides | Notes | [Lok06], [SS91] |

11 | 09/30 | Discussion of project topics. | Slides | Notes | |

12 | 10/05 | Hankel matrices and their rigidity. | Slides | Notes | [GT16] |

13 | 10/07 | Rigidity of Hankel matrices. | Slides | Notes | [GT16] |

14 | 10/12 | Rigidity in sub-exponential time, rigidity of sparse matrices. | Slides | Notes | |

15 | 10/14 | Orthogonal vectors. | Slides | Notes | [CW16], [AC19] |

16 | 10/19 | Hierarchy Theorems. | Slides | Notes | [Žák83], [AB09, Sec 3] |

17 | 10/21 | Rectangular PCPs. | Slides | Notes | [AB09, Sec 11], [BHPT20] |

18 | 10/26 | Rigidity in P^{NP}. |
Slides | Notes | [AC19], [BHPT20] |

Homework 2 | |||||

Part III. Limitations of known techniques. | |||||

19 | 10/28 | Limitations of combinatorial methods. | Slides | Notes | [Lok00], [Val75] |

20 | 11/02 | Rigidity of error correcting codes. | Slides | Notes | [Dvi16] |

21 | 11/04 | Hadamard matrix is not rigid. | Slides | Notes | [AW17] |

22 | 11/09 | Croot-Lev-Pach lemma, rigidity of matrices M(x,y)=f(x+y). | Slides | Notes | [DE17] |

23 | 11/11 | Rigidity of Hadamard, Fourier, and Toeplitz matrices. | Slides | Notes | [DL19] |

24 | 11/16 | Natural proofs, inapproximability of rigidity. | Slides | [RR94], [Ale03] | |

25 | 11/18 | Rigidity of a family of circulant matrices. | Slides | [CPR98], [GH20] | |

Part IV. Applications of rigidity. | |||||

26 | 11/30 | Rigidity and circuit lower bounds. | Slides | - | [AW17], [GKW21] |

27 | 12/03 | Rigidity and data structure lower bounds. | Slides | - | [DGW19], [RR20] |

28 | 12/07 | Rigidity and communication complexity. | Slides | - | [Raz89], [Wun12] |

29 | 12/14 | Final Projects. | - | - | - |