Columbia Undergraduate Learning Seminar in Theoretical Computer Science

About

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.


Join Us!

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.


Spring 2025

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.

The sum-of-squares method for algorithms

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-SOoS 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

Property Testing on Boolean Functions

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

Previous Semesters

Fall 2024

Summer 2024

Spring 2024

Fall 2023

Spring 2023

Fall 2022

Summer 2022

Spring 2022

Fall 2021

Summer 2021