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.
This is the first iteration of the TCS seminar. The seminar is run by: Cassandra Marcussen.
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 |
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) |
Organizer: Alan. Graduate Student Mentor: Clayton.