The Columbia Undergraduate Learning Seminar in Theoretical Computer Science is a student-run seminar for undergraduates at Columbia interested in theoretical computer science. The goal of the learning seminar is to provide undergraduate students with the opportunity to learn about theoretical computer science in a collaborative, student-driven setting and to meet other students interested in theoretical computer science.
The learning seminar is dedicated to providing an inclusive and welcoming environment for all students interested in theoretical computer science. No background in theoretical computer science is required to participate in the seminar, and everyone is welcome to join!
Each semester, the Columbia Undergraduate Learning Seminar in Theoretical Computer Science will hold one or more seminars on topics related to TCS. The presentations will primarily be given by students, which is a great opportunity to gain experience giving a technical talk in TCS and meet other students interested in the topic.
The seminar is currently run by Ekene Ezeunala. If you have any questions or would like to join the seminar's Slack channel, please email him here.
Sign up for the mailing list here: Mailing List Sign-Up.
This summer semester, we will be holding groups on matrix rigidity and the complexity of differential privacy. Each group is run by an undergraduate student organizer and advised by a graduate student mentor. The groups meet roughly weekly and should be approachable for students of all ranges of prior exposure to TCS.
Please see the descriptions and tables below for a summary and the list of talks for each of the groups.
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 |
Spring 2024 |
Fall 2023 |
Spring 2023 |
Fall 2022 |
Summer 2022 |
Spring 2022 |
Fall 2021 |
Summer 2021 |