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 Jonah Stockwell. If you have any questions or would like to get involved with the seminar, please email him here.
This fall semester, we will be holding groups on the high-dimensional geometry and on interactive proof systems. 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.
Organizers: Jonah and John. Graduate student mentor: Yizhi.
Description: In the modern age, from LLM embeddings to customer statistics, data is incredibly high-dimensional. However, when problems scale to high dimensions, we find the "curse of dimensionality," that many problems are much harder to solve in high dimensions. Thus, in the face of high-dimensionality, we develop new tools to efficiently reason about and solve these problems. In this seminar, we will learn how to think about high-dimensional problems and how to design efficient algorithms to solve these problems. Prerequisites: Comfort with linear algebra, some probability theory, and the design of algorithms. Previous theory courses are helpful, but not necessary.
| Date | Topic | Reading | Speaker |
|---|---|---|---|
| September 30th | Introduction. | Chap. 2 of Hopcroft-Kannan Chap. 1-2 of Vershyn Book Lec. 1 of Vershyn Course Andoni Slides |
Jonah and John |
| October 7th | Convexity and Caratheodory Theorem | Lec. 2 of Vershyn Course Chap. 1 of Vershyn Book |
Jonah |
| October 21st | Dimension Reduction (Johnson-Lindenstrauss) | Chap. 2.7 of Hopcroft-Kannan Chap. 5 of Vershyn Book Arora Notes Lee Course |
Jonah |
| October 28th | SVD and Intrinsic Dimensionality. | Arora Notes | Hao |
| November 11th | Extensions of SVD | Vershyn Book | John |
| November 18th | Space Partitions, Locality-Sensitive Hashing, and NNS. | Andoni Slides
Chap. 8 of Hopcroft-Kannan Lee Notes |
Ken |
| November 25th | Discrete Fourier Transform and its Uses | Chap. 8 of Arora Course | Aruzhan |
| December 2nd | Method of Types, Sanov's Theorem. | various | Chenyang |
Organizers: Mark and Hao. Graduate student mentor: William.
Description: Interactive proof systems are powerful tools that have found surprising applications, such as in machine learning, quantum, and cryptography. As you may know, one of the definitions of NP is the set of all proofs whose verifications are efficient. Interactive proof systems started, more or less, to capture this interaction between a prover and a verifier. In this reading group, we will survey some powerful interactive proof protocols behind many surprising recent results. For a few examples, we will hopefully see how the sumcheck protocol helped show IP=PSAPCE, how it also helped reduce #SAT hardness on average to an average-case hard Nash equilibrium distribution, how Zero-Knowledge proofs can be realized in classical and quantum worlds, how classical verifiers can be used to verify quantum computations, and/or how LLMs can check their own correctness and iterate on their outputs. Based on participants’ interests, we can focus on a few of these aspects of interactive proof systems; let’s decide the first time we meet!
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| October 20th | Introduction + Basics of Interactive Proof Systems (Private & Public Randomness) | Mark | Chap. 8.1-8.4 of Arora-Barak Lec. 1-2 of Rothblum |
| October 27th | Sumcheck protocol (IP=PSPACE) and Fiat-Shamir Transformation (from interactive to non-interactive proofs) — Particularly, we will study how to make suncheck protocol non-interactive via Fiat-Shamir as an example | Hao | Chap. 8.5 of Arora-Barak Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir |
| November 10th | Selected by Presenter | TBD | Jonah and Mark |
| November 17th | Selected by Presenter | TBD | Jonah |
| November 24th | Selected by Presenter | TBD | TBD |
| December 1st | Selected by Presenter | TBD | TBD |
| December 8st | Selected by Presenter | TBD | TBD |