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.
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 Fall semester, we will be holding three groups, each focused on a different topic within TCS. The groups are: Algebraic and Spectral Graph Theory, Analysis of Boolean Functions, and Theoretical Neuroscience. Each group is run by an undergraduate student organizer along with 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. Graduate Student Mentor: Binghui.
Description: We explore a variety of topics in spectral and algebraic graph theory, following the book of the same name by Daniel Spielman. Some of the topics we will cover include random walks, rubber bands, and electronic networks. The seminar will build up towards a discussion of one of the seminal results in this area, a fast algorithm for solving linear systems.
| Resource | Title | Link |
|---|---|---|
| Spielman | Spectral and Algebraic Graph Theory | Link |
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| September 30th | Introduction, Motivation, and Background. The Spectral Theorem. | Ekene | Spielman Chap. 1; Fan R. K. Chung Lectures on Spectral Graph Theory Chap. 1 |
| October 7th | Courant-Fischer Theorem. The graph Laplacian. | Ekene | Spielman Chaps. 2, 3 |
| October 14th | Random Walks and Diffusion Problems. | Adi | Spielman Chap. 10 |
| October 21st | Electrical Networks and Graphs. | Ryan | Spielman Chaps. 11, 12 |
| October 28th | Midterm Break | ||
| November 4th | Sampling Spanning Trees. | Ayaan | Spielman Chap. 13 |
| November 11th | Graph Sparsifiers. | Binghui | Spielman Chap. 14 |
| November 18th | Cheeger's Inequality. | Lyra | Spielman Chap. 21 |
| December 2nd | Laplacian solvers, and a nearly-linear-time Laplacian Solver | Ekene and Binghui | Spielman Chap. 36; [ST'04]; [KMP'10]; [KLOS'14]; [Madry'13] |
Organizers: Ashwin and Krish. Graduate Student Mentor: Yuhao.
Description: We cover foundational concepts in Boolean function analysis, a widely applicable tool in theoretical computer science. We will go through the first two chapters of Ryan O'Donnell's Analysis of Boolean Functions textbook, culminating in an algorithm for linearity testing and a result in voting theory.
| Resource | Title | Link |
|---|---|---|
| O'Donnell | Analysis of Boolean Functions | Link |
| Date | Topic | Speaker | Reading | Optional Exercises |
|---|---|---|---|---|
| October 2nd | Background | Krish and Ashwin | O'Donnell Sec. 1.1 - 1.3 | 1.1 (a-c, g-i), 1.2, 1.3, 1.4, 1.5 |
| October 9th | Parseval's Identity | Ashwin and Krish | O'Donnell Sec. 1.4 | 1.6, 1.7, 1.13, 1.15 |
| October 16th | Convolution | Szymon | O'Donnell Sec. 1.5 | 1.20, 1.21, 1.23, 1.24 |
| October 23rd | BLR Linearity Testing | Nikhil | O'Donnell Sec. 1.6 | |
| October 30th | Influences and Derivatives | Srirag | O'Donnell Sec. 2.12 - 2.22 | |
| November 6th | Academic Holiday | |||
| November 13th | Poincare Inequality | Krish and Ashwin | O'Donnell Sec. 2.27 - 2.38 | |
| November 20th | Noise Stability | Assigned Reading | O'Donnell Sec. 2.40 - 2.47 | |
| November 27th | The Noise Operator | Assigned Reading | O'Donnell Sec. 2.49 - 2.54 | |
| December 4th | Arrow's Theorem | Yuhao | O'Donnell Sec. 2.5 |
Organizer: Shujun. Graduate Student Mentor: Daniel.
Description: We explore topics in theoretical neuroscience as it relates to artificial intelligence. Talks themselves will focus on the mathematical and computational cores of the weekly topic, with both proof-based and computational work. Optionally, there will be a topic-related project that may develop into a paper for interested students.
| Resource | Title | Link |
|---|---|---|
| Gerstner | Neuronal Dynamics | Link |
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| October 5th | Introduction and Background: Tools of the Trade | Shujun | Gerstner Chaps. 1-4; [PTHW'21] |
| October 12th | Vision: Convolutional Networks and Beyond | Joseph | [RP'21]; [BSJKP'21] |
| October 19th | Long Short-Term Memory and Transformers | Sammy | [HS'97]; [Vaswani et al. (2017)]; [CDKKLH'22] |
| October 26th | Spiking Neural Networks: Boom or Bust? | Paarth | [TGKMM'19]; [LP'20] |
| November 2nd | Attractor Networks: How is memory preserved in networks? | Gerstner Chap. 17; [PAB'23] | |
| November 9th | Beyond Backpropagation: Deep Learning with Different Learning Rules | Sreyas | Gerstner Chap. 19; [Amit'19]; [JRGM'23] |
| November 16th | Biologically Constrained Deep Learning | Audrey | Gerstner Chap. 20; [BB'06]; [SC'23] |
| November 30th | Large Language Models and Theory of Mind | everyone | General Discussion |