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, examine 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 |
L. Valiant (1977), "Graph-theoretic arguments in low-level complexity”
E. Viola (2016), "On the power of small-depth computation” |
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 |
Spring 2024 |
Fall 2023 |
Spring 2023 |
Fall 2022 |
Summer 2022 |
Spring 2022 |
Fall 2021 |
Summer 2021 |