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.

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.

Organizer: Anushka. Graduate Student Mentor: Oliver.

SUMMARY

Date | Topic | Presenter | Notes and Links |
---|---|---|---|

TBD | TBD | TBD | |

TBD | TBD | TBD |

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 |

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

Organizer: Alan. Graduate Student Mentor: Clayton.

SUMMARY

Date | Topic | Presenter | Notes and Links |
---|---|---|---|

TBD | TBD | TBD | |

TBD | TBD | TBD |