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 and meet other students interested in the topic.
The seminar is currently run by Ekene Ezeunala. If you have any questions or would like to join the seminar's Slack channel, please email him here.
This fall semester, we will be holding groups on additive combinatorics and TCS, on decentralized finance and game theory, and on a broad view of the basic toolkit of the TCS researcher. Each group is run by an undergraduate student organizer and advised by a graduate student mentor. The groups meet roughly 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: Ekene. Graduate student mentor: Yuhao.
Description: Additive combinatorics is an active area of research that bridges combinatorics, number theory, harmonic analysis, and ergodic theory, focusing on the structure of "approximate algebraic" objects and their behaviour under operations like addition and multiplication. In this seminar, we will cover basic topics and recent developments in the field, highlighting applications to fundamental problems in theoretical computer science.
| Resource | Title | Link |
|---|---|---|
| TV | Additive Combinatorics by Tao and Vu | Link |
| S | Additive Combinatorics and its Applications in TCS by Lovett | Link |
| Date | Topic | Reading |
|---|---|---|
| Week 1 | Introduction and the probabilistic method. Basics of set addition, Rusza distance, Plunnecke-Rusza theorem, Frieman theorem | Lovett, Tao-Vu |
| Week 2 | The PFR theorem. Property testing: definitions, linearity testing, testing linear maps and a connection to the PFR theorem | Lovett |
| Week 3 | Statistical set addition: Balog-Szemeredi-Gowers (BSG) theorem | Lovett, Tao-Vu |
| Week 4 | Applications to a fast algorithm for 3-SUM with pre-processing | Various |
| Week 5 | Arithmetic progressions: statement of important results (van der Waerden, Szemeredi, Green-Tao, Kelley-Meka); set without arithmetic progressions (Behrend construction) | Tao-Vu |
| Week 6 | Ruzsa-Szemeredi graphs. Application: impossibility of witness compression for NP languages | Lovett |
| Week 7 | Communication complexity I | Various |
| Week 8 | Communication complexity II | Various |
| Week 9 | Polynomial method: the cap-set problem and connections to matrix multiplication algorithms | Lovett, Tao-Vu, extras |
Organizer: Akash. Graduate student mentor: Jason.
Description: This group will dive into the fundamentals of decentralized finance and game theory, focusing on the theory related to incentive alignment of actors with the goal of designing new mechanisms or studying ones that are in experimental phases. Decentralized finance is all about implementing functions of traditional finance (like lending or exchanging assets) without intermediation or trusted third parties. Topics will be assorted and chosen based on specific participants’ interests. The goal will be to engage in active research topics, and there are many approachable open questions ready for exploration.
Reach out to Jason Milionis for more information about the seminar.Organizer: Jonah. Graduate student mentor: Styopa.
Description: We will follow the great CMU course of the same name and “take a random walk through various mathematical topics that come in handy for theoretical computer science.” The only real prerequisite is some degree of mathematical maturity and familiarity with mathematical proofs (e.g. from courses like CS theory or discrete maths).
| Resource | Title | Link |
|---|---|---|
| O'Donnell | A Theorist's Toolkit | Link |
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| Week 1 | Asymptotics | Jonah | O'Donnell, Lecture 1 |
| Week 2 | The central limit and Berry-Esseen theorems | John | O'Donnell, Lecture 2 |
| Week 3 | Bounds on tails of probability distributions | Matthew | O'Donnell, Lecture 3 |
| Week 4 | Fields and polynomials | Andrew | O'Donnell, Lecture 9 |
| Week 5 | Information theory | Bo | Chap. 2 of Entropy and Diversity |
| Week 6 | Error-correcting codes | Styopa | O'Donnell, Lecture 10 |
| Week 7 | Expander graphs | Jonah | O'Donnell, Lecture 12 |
| Week 8 | Quantum computation | Ana | O'Donnell, Lecture 22 |
| Week 9 | Cryptography | Zoey | O'Donnell, Lecture 23 |