Columbia Undergraduate Learning Seminar in Theoretical Computer Science


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 Cassandra Marcussen. If you have any questions or would like to join the seminar's Slack channel, please email her here.

Sign up for the mailing list here: Mailing List Sign-Up.

Spring 2022

During Spring 2022, we will be holding four groups, each focused on a different topic within TCS. The groups are: Computational Geometry, High-Dimensional Probability and Applications to CS, Philosophy and Theoretical Computer Science, and Quantum Computing. 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.

Computational Geometry

Organizer: Ari. Graduate Student Mentor: Maryam.

Date Topic Speaker
February 15th Introduction Ari
February 22nd Plane Embeddings Jeffrey
March 1st Packing & Covering
March 22nd Polytopes, Part 1 Jet and Carlos
March 29th Polytopes, Part 2 Jet and Carlos
April 5th Convex Hulls Casey
April 12th Delaunay Triangulations, Part 1 Ashwin and Walt
April 19th Delaunay Triangulations, Part 2 Ashwin and Walt

High-Dimensional Probability and Applications to CS

Organizer: Cassandra. Graduate Student Mentor: Shivam.

Resource Title Link
HDP High-Dimensional Probability: An Introduction with Applications in Data Science Link
Date Topic Speaker Reading
February 5th Introduction, Probability Review, and Concentration Inequalities Cassandra HDP Ch. 1, Ch. 2 Sections 2.1, 2.2
February 12th Hoeffding's and Chernoff's Inequalities Chris HDP Ch. 2 Sections 2.2, 2.3
February 23rd Sub-gaussian Distributions Cassandra HDP Ch. 2 Sections 2.5, 2.6
March 2nd Random Vectors: Concentration of the norm, covariance matrices, and principal component analysis Chris HDP Ch. 3, Sections 3.1 and 3.2
March 23nd Examples of High-Dimensional Distributions Cassandra HDP Ch. 3, Section 3.3
March 30th Grothendiek's inequality and semidefinite programming Savik HDP Ch. 3, Section 3.5
April 6th Maximum cut for graphs Ryan HDP Ch. 3, Sections 3.6, 3.7
April 13th Introduction to Random Matrices and Randomized Singular Value Decomposition Chris HDP Ch. 4, Section 4.1
April 20th Nets, Covering Numbers, Packing Numbers, and Error-Correcting Codes Cassandra HDP Ch. 4, Sections 4.2, 4.3
April 27th Final Meeting

Philosophy and Theoretical Computer Science

Organizer: Yunya. Graduate Student Mentors: Tim and Samara.

Resource Title Link
MIT Philosophy and TCS Course Philosophy and Theoretical Computer Science Link
Date Topic Speaker Reading
February 4th Analytic Philosophy and TCS Yunya
February 11th Notions of Computation Brian Cantwell Smith: The philosophy of computation - meaning, mechanism, mystery
February 18th Mathematical Proof/Definiteness Adiba Aaronson "Why philosophers should care about computational complexity" (Section 9), Shieber "The Turing Test as Interactive Proof"
February 25th TCS, Free will, and Determinism Alex Aaronson lecture notes, Aaronson blog
March 4th Complexity: NP-completeness Joe Aaronson "Why philosophers should care about computational complexity"(Section 4), Aaronson "NP-complete Problems and Physical Reality"
March 25th Complexity: Learning Theory Richard Kelly "Learning theory and epistemology"
April 1st Complexity: Kolmogorov Complexity Anthony De Wolf "Philosophical Applications of Computational Learning Theory" (Section 3), Schmidhuber "A Computer Scientist’s View of Life, the Universe, and Everything"
April 15th Connectionism and Symbolism Yicheng Schneider "The Language of Thought"
April 22nd Evolvability Yunya Livnat and Papadimitriou "Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation", Valiant "Evolvability"
April 29th Algorithmic Game Theory Quintus Scott Alexander "Meditations On Moloch"

Quantum Computing

Organizer: Alex.

Description: We explore the potential of circuits and algorithms that take advantage of quantum phenomena such as superpositions, entangled states, and exponential information managed by Nature. Then moving onto high-level algorithms, the quantum query model, and applications of the Quantum Fourier Transform (like Shor's algorithm which lets us factor large primes efficiently).

Resource Title Link
O'Donnell Quantum Computation and Information Link
Yuen Introduction to Quantum Computing Link
Nielson and Chuang Quantum Computation and Quantum Information Textbook
Date Topic Discussion Leader Reading
February 6th Classical Boolean Circuits to Quantum Circuits Alex O'Donnell 1
February 13th Math of Quantum States and Quantum Computation Christine O'Donnell 2. Supplemental Readings: Nielson and Chuang 1.2-1.3.4, Prof. Yuen's Worksheet 1 and 2
February 20th No-Cloning Theorem, Quantum Teleportation, CSHS Game Tony O'Donnell 3
February 27th Oracles and Grover's Algorithm Phil O'Donnell 4
March 25th The Quantum Query Model, Deutsch-Josza, Starting Simon's Problem Alex O'Donnell 5, Section 5.2 of Yuen 3
April 1st Simon's Problem cont. Christine Yuen 4, O'Donnell 6

Previous Semesters

Fall 2021

Summer 2021