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.
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.
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.
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 |
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 |
Organizer: Yunya. Graduate Student Mentors: Tim and Samara.
| Resource | Title | Link |
|---|---|---|
| MIT Philosophy and TCS Course | Philosophy and Theoretical Computer Science | Link |
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 |