Columbia Undergraduate Learning Seminar in Theoretical Computer Science

About

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.


Join Us!

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.


Fall 2023

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.

Algebraic and Spectral Graph Theory

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]

Analysis of Boolean Functions

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

Theoretical Neuroscience and Artificial Intelligence

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

Previous Semesters

Spring 2023

Fall 2022

Summer 2022

Spring 2022

Fall 2021

Summer 2021