During Fall 2024, we held three reading groups in additive combinatorics, decentralised finance and game theory, and the theorist's toolkit.
Please see the descriptions and tables below for a summary and the list of talks for each of the groups.
This was the 10th iteration of the TCS seminar. The seminar was run by Ekene Ezeunala.
Organizer: Ekene. Graduate student mentor: Yuhao.
Description: Additive combinatorics is an active area of research that bridges combinatorics, number theory, harmonic analysis, and ergodic theory, focusing on the structure of "approximate algebraic" objects and their behaviour under operations like addition and multiplication. In this seminar, we will cover basic topics and recent developments in the field, highlighting applications to fundamental problems in theoretical computer science.
| Resource | Title | Link |
|---|---|---|
| TV | Additive Combinatorics by Tao and Vu | Link |
| S | Additive Combinatorics and its Applications in TCS by Lovett | Link |
| Date | Topic | Reading |
|---|---|---|
| Week 1 | Introduction and the probabilistic method. Basics of set addition, Rusza distance, Plunnecke-Rusza theorem, Frieman theorem | Lovett, Tao-Vu |
| Week 2 | The PFR theorem. Property testing: definitions, linearity testing, testing linear maps and a connection to the PFR theorem | Lovett |
| Week 3 | Statistical set addition: Balog-Szemeredi-Gowers (BSG) theorem | Lovett, Tao-Vu |
| Week 4 | Applications to a fast algorithm for 3-SUM with pre-processing | Various |
| Week 5 | Arithmetic progressions: statement of important results (van der Waerden, Szemeredi, Green-Tao, Kelley-Meka); set without arithmetic progressions (Behrend construction) | Tao-Vu |
| Week 6 | Ruzsa-Szemeredi graphs. Application: impossibility of witness compression for NP languages | Lovett |
| Week 7 | Communication complexity I | Various |
| Week 8 | Communication complexity II | Various |
| Week 9 | Polynomial method: the cap-set problem and connections to matrix multiplication algorithms | Lovett, Tao-Vu, extras |
Organizer: Akash. Graduate student mentor: Jason.
Description: This group will dive into the fundamentals of decentralized finance and game theory, focusing on the theory related to incentive alignment of actors with the goal of designing new mechanisms or studying ones that are in experimental phases. Decentralized finance is all about implementing functions of traditional finance (like lending or exchanging assets) without intermediation or trusted third parties. Topics will be assorted and chosen based on specific participants’ interests. The goal will be to engage in active research topics, and there are many approachable open questions ready for exploration.
Reach out to Jason Milionis for more information about the seminar.Organizer: Jonah. Graduate student mentor: Styopa.
Description: We will follow the great CMU course of the same name and “take a random walk through various mathematical topics that come in handy for theoretical computer science.” The only real prerequisite is some degree of mathematical maturity and familiarity with mathematical proofs (e.g. from courses like CS theory or discrete maths).
| Resource | Title | Link |
|---|---|---|
| O'Donnell | A Theorist's Toolkit | Link |
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| Week 1 | Asymptotics | Jonah | O'Donnell, Lecture 1 |
| Week 2 | The central limit and Berry-Esseen theorems | John | O'Donnell, Lecture 2 |
| Week 3 | Bounds on tails of probability distributions | Matthew | O'Donnell, Lecture 3 |
| Week 4 | Fields and polynomials | Andrew | O'Donnell, Lecture 9 |
| Week 5 | Information theory | Bo | Chap. 2 of Entropy and Diversity |
| Week 6 | Error-correcting codes | Styopa | O'Donnell, Lecture 10 |
| Week 7 | Expander graphs | Jonah | O'Donnell, Lecture 12 |
| Week 8 | Quantum computation | Ana | O'Donnell, Lecture 22 |
| Week 9 | Cryptography | Zoey | O'Donnell, Lecture 23 |