Explore cutting-edge theoretical computer science research in this Allen School Colloquium featuring talks on revenue maximization, multiplier commutativity verification, efficient data structures, the Santa Claus problem, and counting stable matchings. Gain insights into interdimensional revenue optimization, proof complexity in SAT-solvers, nearly-optimal binary search trees for non-adaptive computations, approximation algorithms for gift assignment, and the growth rate of stable matchings. Delve into topics like combinatorial optimization, propositional logic, and stable matching theory through accessible presentations by PhD students working on algorithms, incentives, economics, proof complexity, communication complexity, information theory, and probabilistic combinatorics.
Money, Circuits, Mythic Figures, and More - Theory in the Allen School
Paul G. Allen School via YouTube
Overview
Syllabus
Intro
Binary Search Trees
Non-Adaptive Insertions
Sunflower Lemma [ErdosRado60]
Using Sunflowers
Combinatorial optimization
Approximation algorithms
The Santa Claus problem
Overview on SC & Makespan Scheduling
Propositional Logic and the SAT problem • Propositional logic reasons with Boolean formulas
Verifying commutativity is already hard
Application and Directions
Maximizing Revenue
Interdimensional: The FedEx Setting
FedEx Truthfulness
Example
How can we learn the function?
Stable Matching Theory: The Basics
Step 1
Taught by
Paul G. Allen School
