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 fall semester, we will be holding groups on network games and algorithmic game theory, automated theorem proving, and circuit complexity. 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.
Organizer: Sam Ferrera. Graduate student mentor: TBD.
Description: Networks provide a natural framework for modeling economic and social interactions. This seminar will examine network-based models of economic behavior, aiming to understand how the properties and structure of a network affect economic outcomes (such as welfare), as well as what can be feasibly computed, learned, or coordinated. We will discuss the formation, stability, and optimality of networks; learning and the diffusion of information through local interactions; decentralized coordination; and the design of networks (or interventions on networks). We will study networks through both the lens of economics, which both motivates which models and outcomes we study, and theoretical computer science, and in particular algorithmic game theory, which helps us understand what we can or cannot do (learn, coordinate, compute) with networks.
| Date | Topic | Reading | Speaker |
|---|---|---|---|
| Introduction | Sam |
Organizer: Oren Hartstein. Graduate student mentor: TBD.
Description: This seminar will explore the use of computer programs to autonomously find proofs to mathematical statements and logical propositions. We will trace the historical development of automated theorem proving across Boole’s mechanization of logic, Hilbert’s decision problem (Entscheidungsproblem), SAT solving, Resolution algorithms, type theory, and modern formal verification systems. Understanding the theory behind automated theorem proving will help contextualize recent advancements from LLMs and provide a better understanding of the future of computer-aided mathematics.
| Date | Topic | Reading | Speaker |
|---|---|---|---|
| Introduction | Oren |
Organizer: Jonah Stockwell. Graduate student mentor: TBD.
Description: How difficult is it to compute a Boolean function? Circuit complexity attempts to rigorously answer this question by studying the size and depth of circuits computing particular functions. In addition to attempting to answer this elusive, fundamental question, results in circuit complexity have borne great fruit in many areas of theoretical computer science, including cryptography, learning theory, parallel algorithms, proof complexity, and more.
In this seminar, we will explore both the classical results and techniques in circuit complexity and the interesting impact circuit lower bounds have had on other areas of theoretical computer science. Topics may include formula and monotone circuit lower bounds, AC⁰ and random restrictions, the Razborov–Smolensky method, communication complexity and Karchmer–Wigderson games, threshold circuits, Natural Proofs, hardness versus randomness, algorithms for circuit SAT, arithmetic circuits, learning theory, proof complexity, and modern developments in meta-complexity and MCSP.
| Date | Topic | Reading | Speaker |
|---|---|---|---|
| Introduction | Jonah |