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 2nd | Cheeger's and Grothendieck's inequalities in the normal and SOS form, connections to SoS certificates and pseudodistributions, connections to spectral algorithms. | Section 1 of BS | Ken |
| April 9th | Game theory in the SoS world. Review of the notions of strategic game, mixed strategy, value of a game, Nash equilibrium. Statements of the von Neumann, Nash (and Kakutani fixed-point), and Glicksberg theorems; proof sketches of the same. Polynomial games; SoS certificate as an equivalence between the adjoint of a Hankel map and a vector of polynomial coefficients and determining the value and atomic strategies of polynomial & semialgebraic games via SoS. | [Parrilo] | Ekene |
| April 16th | A poly-time SOS algorithm for min-cut via finding suitable pseudodistributions. Well-separated sets in a metric space, and the (strong) global structure theorem. Conductance and the sparsest cut problem; the Arora-Rao-Vazirani approximation algorithm. | Section 4.1 of BS | Ekene |
| April 23rd | Mixture models for separated isotropic Gaussian clusters. Polynomial constraints for cluster indicators; an SoS algorithm via pseudoexpectations over explicitly bounded distributions. Rounding the pseudomoments to get a clustering algorithm. | Schramm notes | Marcella |
| April 30th | Review of the introductory SOS material from earlier in the semester. Putinar's Positivstellensatz and applications to conic optimisation programs and semidefinite programming. Using the polynomial interpolant basis and the SOS technique to obtain faster interior-point methods for SOS optimisation. | [Jiang, Natura, Weinstein] | Shunhua |
| May 7th | The unique games conjecture and connections to sum of squares algorithms. | various | Ekene |
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 |
| March 14th | Monotonicity testing, part two | Hao | A Polynomial Lower Bound for Testing Monotonicity |
| March 28th | Monotonicity testing, part three | Mark | Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness |
| April 4th | Monotonicity testing, part four | Hao | On Monotonicity Testing and Boolean Isoperimetric-type Theorems |
| April 11th | k-Junta testing, part one | Mark | Selections from Chapter 5 of Goldreich |