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!

Sign up for the mailing list here: Mailing List Sign-Up. If you have any questions, please email Cassandra Marcussen.

Fall 2021

During Fall 2021, we will be holding three groups, each focused on a different topic within TCS. The groups are: A Theorist's Toolkit, Combinatorics and Graph Theory, and Deep Learning Theory. Each group is run by an undergraduate student organizer, and some groups have a graduate student mentor. The groups meet 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.

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
December 9th TBD TBD O'Donnell Lecture 16
December 16th Cryptography Alan O'Donnell Lecture 23

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 study important techniques that are used in combinatorial proofs. Our focus is in graph theory, 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 TBD
December 3rd Roth's Theorem Jet GTAC Ch. 3.3
December 10th TBD Mark and Geoffrey TBD
December 17th TBD TBD TBD

Deep Learning Theory

Organizer: Ari. Graduate Student Mentor: Clayton.

Resource Title Link
Goodfellow Deep Learning Link
Date Topic Discussion Leader 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 TBD Alexandra TBD
November 16th TBD Berkan and Kevin TBD
November 23rd TBD Francesca TBD
November 30th TBD Andrew TBD
December 7th TBD Clayton or Guest Lecture TBD

Summer 2021