Columbia Undergraduate Learning Seminar in Theoretical Computer Science

Fall 2023

During Fall 2023, we held three groups, each focused on a different topic within TCS. The groups were: Algebraic and Spectral Graph Theory, Analysis of Boolean Functions, and Theoretical Neuroscience and AI. Each group was run by an undergraduate student organizer along with a graduate student mentor.

Please see the descriptions and tables below for a summary and the list of talks for each of the groups.

This was the seventh iteration of the TCS seminar. The seminar was run by Ekene Ezeunala.

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