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.


Join Us!

Sign up for the mailing list here: Mailing List Sign-Up. If you have any questions, please email Cassandra Marcussen.

Summer 2021

During Summer 2021, we will be holding four groups, each focused on a different topic within TCS. The groups are: NP-Completeness, Analysis of Boolean Functions and Property Testing, Algorithmic Game Theory, and Computational Learning Theory. Each group is run by an undergraduate student organizer and a graduate student mentor. The groups meet 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.

NP-Completeness Group

Organizer: Anushka. Graduate Student Mentor: Oliver.

SUMMARY

Date Topic Presenter Notes and Links
TBD TBD TBD
TBD TBD TBD

Analysis of Boolean Functions and Property Testing Group

Organizer: Cassandra. Graduate Student Mentor: Shivam.

SUMMARY

Books Title Link
O'Donnell Analysis of Boolean Functions Link
Date Topic Speaker Materials Covered Reading and Exercises to be completed before the meeting
May 30th Introduction to the Analysis of Boolean Functions Shivam Beginning of O'Donnell Ch. 1, and survey of related topics. None
June 6th Boolean functions and the Fourier expansion (continued) Cassandra Remainder of O'Donnell Ch. 1 O'Donnell Chapter 1. Exercises 1.1 a, g, i h and 1.2.
June 13th Social choice functions, influences, and noise stability Shivam O'Donnell Ch. 2 O'Donnell Chapter 2, exercises TBD
June 20th Social choice functions, influences, and noise stability (continued) Gregory O'Donnell Chapter 2 TBD
June 27th TBD Chris
July 4th TBD Ahmed
July 11th TBD Panchi
July 18th TBD Andrei
July 25th TBD Erica
August 1st TBD Ari
August 8th TBD Gregory
August 15th TBD TBD

Algorithmic Game Theory Group

Organizer: Adiba. Graduate Student Mentor: Kiran.

Description: We will focus on the study of various notions of equilibria in game theory with an emphasis on the computational tractability of finding equilibria. We also study the price of anarchy, connections between game dynamics (learning in games) and equilibria, and recent notions of solution concepts for games that go beyond classic notions of equilibria.

Books Title Link
AGT Algorithmic Game Theory Link
TLAGT Twenty Lectures on Algorithmic Game Theory Link (downloads a PDF)
GTA Game Theory Alive Link
Date Topic Speaker Materials Covered Other References
June 6th Game Theory Intro: Games + Equilibria Definitions Melody Ch 1.1 - 1.6 of AGT, Ch. 13 of TLAGT, overview of Nash's theorem (see references) A Tutorial on the Proof of the Existence of Nash Equilibria (Jiang and Leyton-Brown); Ch. 5 of GTA
June 13th Selfish Routing + Price of Anarchy Andrew Ch. 11 + 12 of TLAGT Worst-Case Equilibria (original PoA paper, Koutsoupias and Papadimitriou); The Price of Anarchy (nice article, Robinson)
June 20th Strong Nash Equilibria Mirah Ch. 15 of TLAGT
June 27th Complexity of Pure Nash Equilibria Adiba Ch. 19 of TLAGT, Ch. 2 of AGT
July 4th No meeting
July 11th Complexity of Mixed Nash Equilibria Ashwin Ch. 20 of TLAGT, Ch. 2 of AGT Simple writeup of PPAD proof: The Complexity of Computing a Nash Equilibrium (Daskalakis, Goldberg, Papadimitriou). If you're also curious about approximation: On the Complexity of Approximating a Nash Equilibrium (Daskalakis).
July 18th Complexity of Correlated Equilibria Alex Computing Correlated Equilibria in Multi-Player Games (Papadimitriou and Roughgarden)
July 25th Game Dynamics + Learning Ananya Ch. 16, 17 of TLAGT
August 1st Game Dynamics + Learning cont. Ian Ch. 17, 18 of TLAGT, Ch. 4 of AGT (some duplicate material from last week in Ch. 4)
August 8th Strategizing against No-Regret Learners Quintus Strategizing against No-regret Learners (Deng, Schneider, Sivan)
August 15th Game Dynamics as the Meaning of the Game Casey Game Dynamics as the Meaning of a Game (Papadimitriou and Piliouras)
Extra Topic Smooth Games + Fast Convergence TBD Ch. 14 of TLAGT; Intrinsic Robustness of the Price of Anarchy (Roughgarden); Fast Convergence of Regularized Learning in Games (Syrgkanis, Agarwal, Luo, Schapire)

Computational Learning Theory Group

Organizer: Alan. Graduate Student Mentor: Clayton.

SUMMARY

Date Topic Presenter Notes and Links
TBD TBD TBD
TBD TBD TBD