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 and meet other students interested in the topic.
The seminar is currently run by Jonah Stockwell. If you have any questions or would like to get involved with the seminar, please email him here.
This spring semester, we will be holding groups on algorithmic game theory and randomness. Each group is run by an undergraduate student organizer and advised by a graduate student mentor. The groups meet roughly 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.
Organizers: Jonah and John. Graduate student mentor: Yuhao.
Description: With the emergence of the Internet, game theory, which had found a home in economics, was united with theoretical computer science, leading to the field of algorithmic game theory. Now, the field of algorithmic game theory has grown tremendously in the past 30 years. In this seminar, we will study a number of results in algorithmic game theory, ranging from algorithmic design to computational complexity and infeasibility to applications in learning and networking. More specifically, topics we may cover include methods for and the complexity of computing equilibria, TFNP, price of anarchy, algorithmic fairness, algorithmic mechanism design, and auction theory. We aim to cater to both a classical economic game theory and a theoretical computer science audience, if you have experience in either one, this is a great opportunity to learn from others and for others to learn from you!
| Date | Topic | Reading | Speaker |
|---|---|---|---|
| February 19 | Introduction | Game Theory History Roughgarden Course |
Jonah |
| February 26 | Mechanism Design | https://timroughgarden.org/f13/l/l2.pdf | Jonah |
| March 5 | Price of Anarchy and Price of Stability | https://www.cs.cornell.edu/courses/cs6840/2012sp/ https://timroughgarden.org/f13/f13.html |
John |
| March 12 | TFNP, the Complexity of AGT, and Finding Nash Equilibria | https://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf https://www2.math.upenn.edu/~ryrogers/AGT.pdf |
Yuhao |
| March 26 | A Proof of PPAD-completeness of Nash | Jonah | |
| April 2 | No-Regret Learning Implies Correlated Equilibria | Eric | |
| April 9 | Mechanism Design without Money | Jonah | |
| April 16 | TBD | TBD | |
| April 23 | TBD | TBD |
Organizers: Mark, Hao, and Jonah. Graduate student mentor: William.
Description: Randomness is a powerful algorithmic tool, yielding us some of the most efficient and effective algorithms for many problems. Moreover, randomness is a fascinating, and difficult line of study in computational complexity, with the question of whether randomness actually makes problems easier to solve efficiently remaining a core unsolved problem (P vs. BPP). In this seminar, we will explore a variety of topics related to the use of randomness in solving algorithmic problems and in computational complexity. This seminar will be very flexible, as we will begin by covering a few core concepts, and then we will explore whichever topics the participants wish to discover. Topics we will potentially cover include derandomization, pseudorandomness, the probabilistic method, martingales, probabilistic proof systems, random walks, Fourier growth, and privacy.
| Date | Topic | Speaker | Reading |
|---|---|---|---|
| February 20 | Introduction, “The Power? Of Randomness,” The Probabilistic Method | Jonah | |
| February 27 | Lovasz Local Lemma | Jonah | |
| March 6 | Szemerédi Regularity Lemma | Jonah | |
| March 27 | Martingales | Ken | |
| April 3 | Psuedorandomness | Jonah | |
| April 10 | PCP Theorem | Hao | |
| April 17 | TBD | Hao / Jonah | |
| April 24 | TBD | Mark |