During Summer 2024, we held two reading groups in matrix rigidity and the complexity of differential privacy.
Please see the descriptions and tables below for a summary and the list of talks for each of the groups.
This was the ninth iteration of the TCS seminar. The seminar was run by Ekene Ezeunala.
Organizer: Ekene.
Description: Matrix rigidity is a notion that gets at how far a given matrix is to the set of matrices with “small-enough” rank. Although initially introduced to answer a question about which matrices are hard to compute by Boolean circuits, this notion has revealed interesting connections between computation, algebra, combinatorics, and geometry. In this short group seminar, we will introduce matrix rigidity, go over some of the central questions in the area, and then round off with a discussion of some applications.
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| July 6th | Introduction; existence of rigid matrices, barriers | Ekene |
Valiant, 1977
Viola, 2016 |
| July 13th | Rigidity of specific families of matrices, (sufficient) explicitness | Anthony |
Codenotti-Pudlak-Resta, 1998
Dvir-Liu, 2021 Golovnev-Haviv, 2020 |
| July 20th and 27th | Some rigidity lower bounds | Ekene and Eric |
Friedman, 1990
Pudlak-Rodl, 1994 Shokrollahi-Spielman-Stemann, 1997 |
| August 3rd | Rigidity and circuit lower bounds | Yixin |
Alman-Williams, 2017
Golovnev-Kulikov-Williams, 2020 |
| August 10th and 11th | Rigidity and (static) data structure lower bounds | Ekene |
Dvir-Golovnev-Weinstein, 2019
Ramamoorthy-Rashtchian, 2019 |
| August 17th | Rigidity and error-correcting codes | Eric |
Dvir, 2011
Dvir, 2016 |
Organizer: Mark.
Description: Differential privacy is a theoretical framework for ensuring the privacy of individual-level data when performing statistical analysis of privacy-sensitive datasets. In this group seminar we will see an introduction to and overview of differential privacy, with the goal of conveying its deep connections to a variety of other topics in computational complexity, cryptography, and theoretical computer science at large.
| Resource | Title | Link |
|---|---|---|
| Vadhan | The Complexity of Differential Privacy | Link |
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| July 7th | Flavor of cryptography (CPA); randomised response, Laplace mechanism, post processing, and group privacy | Mark | Chapter 1, 2.1 of Vadhan |
| July 14th | Global sensitivity, local sensitivity, propose-test-release | Mark | Chapter 3 of Vadhan |
| July 21st | Information theoretic lower bounds I: reconstruction attacks and discrepancy | Mark | Chapter 5.1 of Vadhan |
| July 28th | Information theoretic lower bounds II: packing lower bounds, fingerprinting lower bounds | Mark | Chapter 5.2,3 of Vadhan |
| August 4th | Computational lower bounds: traitor-tracing lower bounds, and lower bounds for synthetic data | Mark | Chapter 6.1 of Vadhan |
| August 11th | Private PAC learning I: basics | Mark | Chapter 7, 8 of Vadhan |
| August 18th | Private PAC learning II | Mark | Chapter 8 of Vadhan |
| August 25th | Multiparty differential privacy | Mark | Chapter 9 of Vadhan |