Columbia Undergraduate Learning Seminar in Theoretical Computer Science

Summer 2021

During Summer 2021, we will be holding three groups, each focused on a different topic within TCS. The groups are: 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.

Analysis of Boolean Functions and Property Testing Group

Organizer: Cassandra. Graduate Student Mentor: Shivam.

Description: Boolean functions play an important role in many areas of computer science and mathematics, such as in circuit design, graph theory, coding theory, and learning theory. We will study the analysis of Boolean functions, which refers to studying Boolean functions via their Fourier expansion and via analytic methods. We highlight various applications of the analysis of Boolean functions, such as applications in social choice theory, learning, and property testing.

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 from Ch. 1: 1.6, 1.7, 1.13, 1.19. Ch. 2: Ex. 2.3.
June 20th Social choice functions, influences, and noise stability (continued) Gregory O'Donnell Chapter 2 O'Donnell Chapter 2. Exercises: 2.5, 2.11, 2.12, 2.49, 2.53, 2.54, 2.55.
June 27th Spectral structure and learning Chris O'Donnell Chapter 3 O'Donnell Chapter 3. Exercises: 3.8, 3.9, 3.10, 3.14, 3.17
July 4th Introduction to Property Testing: Linearity Testing and Monotonicity Testing Ahmed O'Donnell Ch. 1, Sections 1.5 and 1.6. Lecture notes on property testing (see "Reading") O'Donnell Ch. 1, Sections 1.5 and 1.6. Lecture notes on property testing: Lecture 7 of Sub-Linear Algorithms in Learning and Testing.
July 11th The KKL Theorem and Friedgut's Theorem Panchi O'Donnell's Lecture notes on the KKL Theorem and Friedgut's Theorem O'Donnell's Notes on the KKL Theorem and Friedgut’s Theorem
July 18th Thresholds in Random Graphs and the Russo-Margulis Lemma Alex Notes on the Russo-Margulis Lemma Notes on Russo-Margulis Lemma (see pdf attached via email). Section 8.4 of O'Donnell on p-biased analysis is also a good reference.
July 25th The Linial–Mansour–Nisan algorithm Erica O'Donnell Ch. 4 and Lecture Notes on the LMN algorithm O'Donnell Chapter 4 and Lecture 3 of Sub-Linear Algorithms in Learning and Testing
August 1st Research Highlight and Graduate School Q&A Shivam Related Reading: Quantitative Correlation Inequalities via Semigroup Interpolation (De, Nadimpalli, Servedio)
August 17th Property Testing of Boolean Functions and Research Highlight Professor Xi Chen
August 22nd Pseudorandomness Ari O'Donnell 6.1 and Pseudorandom Generators from Polarizing Random Walks

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