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 spring semester, we will be holding groups on the sum-of-squares method and on property testing for Boolean functions. 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 Ekene. Graduate student mentor: Shunhua.
Description: In this 8/9-week seminar series, we will explore the Sum of Squares (SOS) method, a framework connecting convex optimization, some algebraic geometry, and theoretical computer science. Time permitting, we will study its mathematical foundations as well as algorithmic applications of the technique.
| Resource | Title | Link |
|---|---|---|
| Barak and Steurer | Proofs, beliefs, and algorithms through the lens of sum-of-squares | BS |
| Fleming, Kothari, and Pitassi | Semialgebraic proofs and efficient algorithm design | FKP |
| Date | Topic | Reading | Speaker |
|---|---|---|---|
| February 26th | Introduction via the Fourier analysis of low-degree functions on the Boolean hypercube. The certificate perspective on sum-of-squares. From Caratheodory's theorem to the SOS hierarchy. A "baby" Positivstellensatz. | Various | Ekene |
| March 5th | Existence and explicit constructions for sum-of-squares certificates. Applications: edge connectivity and maximum cut. Quick review of some spectral graph theory and positive semidefinite matrices. Linear and quadratic proofs. | Chapter 4 of FKP, Section 2.1 of BS | Ekene and Jonah |
| March 26th | Showing existence, finding SOS certificates for problems, e.g. random 3SAT. Natural-vs-SOS tractability barriers corresponding to conditional and unconditional lower bounds. Pseudoexpectations, pseudodistributions, and the duality between pseudodistributions and SOS certificates. A Goemans-Williamson SOS algorithm for Max-Cut. | Various sections from BS and FKP | Ekene |
| April 3rd | Cheeger's and Grothendieck's inequalities, connections to SOS | Section 1 of BS | Ken |
Organizer: Mark and Hao.
Description: Sometimes, improving learning algorithms can only do so much, and we must instead pivot to the problem of handling large datasets efficiently. Recent breakthroughs like LLMs owe their success to inventive engineering that leverages massive data. Property testing similarly seeks to establish lower and upper bounds for testing certain properties of many samples in sublinear time. Tightening these bounds is tough: for instance, even for 3SAT, the best lower bound is far from super-polynomial. Researchers thus focus on restricted models like Boolean functions, where the bounds for properties such as monotonicity or k-Junta testing can be nearly tight. In this reading seminar, we will focus on surveying the techniques and analyses on these aspects of property testing.
| Resource | Title | Link |
|---|---|---|
| Goldreich | Property Testing | Goldreich |
| O'Donnell | Analysis of Boolean Functions | O'Donnell |
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| February 28th | Analysis of Boolean functions: Fourier basis and coefficients, the Fourier spectrum, epsilon-fooling | everyone | Selections from Chapters 1, 6, and 7 of the O'Donnell book. |
| March 7th | Testing monotonicity for Boolean functions on the hypercube | Mark | Selections from Chapter 4 of Goldreich |