Columbia Undergraduate Learning Seminar in Theoretical Computer Science

Fall 2021

During Fall 2021, we held three groups, each focused on a different topic within TCS. The groups were: A Theorist's Toolkit, Combinatorics and Graph Theory, and Deep Learning Theory. Each group was run by an undergraduate student organizer, and some groups had 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 second iteration of the TCS seminar. The seminar was run by Cassandra Marcussen.

A Theorist's Toolkit

Organizer: Cassandra.

Resource Title Link
O'Donnell A Theorist's Toolkit Link
Spielman Spectral Graph Theory Link
Date Topic Speaker Reading
September 30th Asymptotics Cassandra O'Donnell Lecture 1
October 7th Central Limit Theorem Anthony O'Donnell Lecture 2
October 14th Chernoff Bounds Chang and Eitan O'Donnell Lecture 3
October 21st Spectral Graph Theory Remy O'Donnell Lecture 6 and Spielman Lecture 1
October 28th Spectral Graph Theory, continued Remy Spielman Lectures 2 and 3
November 4th Fields and Polynomials Anda O'Donnell Lecture 9
November 11th Information Theory Leo Entropy and Diversity Ch. 2
November 18th Error-Correcting Codes Cassandra O'Donnell Lecture 10 and Computational Complexity Section 17.4, 17.5
December 2nd Communication Complexity Luke O'Donnell Lecture 19 and Computational Complexity Ch. 12
December 16th Cryptography Alan O'Donnell Lecture 23 and Introduction to Modern Cryptography (3rd edition) Ch. 1 and 2

Combinatorics and Graph Theory

Organizer: Alex. Graduate Student Mentor: Shivam.

Description: Combinatorics is the study of some of the most foundational discrete structures found throughout mathematics and theoretical computer science. We studied important techniques that are used in combinatorial proofs, focusing on graph theory and looking at inherent structures and extremal properties of networks.

Resource Title Link
GTAC Graph Theory and Additive Combinatorics Link
Date Topic Speaker Reading
October 8th Counting, Combinations, Binomial Theorem Alex Extremal Combinatorics Ch. 1 and Exercises
October 15th Ramsey Theory and Topics Shivam No reading
October 24th The Probabilistic Method Yunya Advanced Cominbatorics Handouts Ch. 4.1, 4.2
October 29th Extremal Graph Theory Casey GTAC Ch. 2.1, 2.2, 2.5
November 5th Linear Algebraic Methods Tianqi Linear Algebra Methods in Combinatorics Ch. 2
November 12th Szemerédi’s Regularity Lemma Remy GTAC Ch. 3.1
November 19th Szemerédi’s Regularity Lemma, continued Remy GTAC Ch. 3.1
December 3rd Roth's Theorem Jet GTAC Ch. 3.3
December 10th Mark and Geoffrey

Deep Learning Theory

Organizer: Ari. Graduate Student Mentor: Clayton.

Resource Title Link
Goodfellow Deep Learning Link
Date Topic Speaker Reading
October 19th Feedforward Networks AJ Goodfellow Ch. 6
October 26th Regularization Mark and Geoffrey Goodfellow Ch. 7
November 2nd Optimization Alfonso and Theo Goodfellow Ch. 8
November 9th Vector Symbolic Architectures Alexandra Vector Symbolic Architectures as a Computing Framework for Nanoscale Hardware
November 16th CNN Basics Berkan and Kevin Goodfellow Ch. 9
November 28th GradCam Berkan and Kevin Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization
December 5th Clayton

Summer 2021