Tentative daily schedule (all times are in US Pacific Daylight Time - PDT)
| Time (PDT) | Activity |
|---|---|
| 7:30-8am | icebreaking activity (TA led; small groups) |
| 8-9:30am | Lecture block 1; ends with homework assigned (entire group) |
| 9:30-10am | Break |
| 10am-11:30am | TA-led problem solving session (small groups) |
| 12-1:30pm | Lecture block 2; ends with homework assigned (entire group) |
| 1:30-2pm | Break |
| 2-3pm | plenary / panel / non-technical talk / other activities |
| Evening | office hours with TAs, opportunity to interact / games / community-building activities |
A Google calendar with links to events will also be shared with the school participants. Please see the program below for lecture schedules and course descriptions.
| Lecture block 1 | Lecture block 2 | |
|---|---|---|
| Monday | José Correa / Andrés Cristi | Gillat Kol |
| Tuesday | Yael Kalai | Andrea Lincoln |
| Wednesday | José Correa / Andrés Cristi | Antonio Blanca |
| Thursday | Gillat Kol | Antonio Blanca |
| Friday | Yael Kalai | Andrea Lincoln |
Course Descriptions
Antonio Blanca: Markov Chain Monte Carlo method
This mini-course will serve as an introduction to the Markov chain Monte Carlo (MCMC) method, one of the most powerful approaches to sampling complex probability distributions. An MCMC algorithm consists of a Markov chain designed to converge to a probability distribution from which we would like to sample efficiently. A fundamental research question in theoretical computer science, discrete mathematics, and other more applied areas is how many steps of the Markov chain are required until its distribution is close to the target distribution.
We will begin with a brief introduction to Markov chains, exploring convergence conditions and standard probabilistic and analytical methods for bounding their speed of convergence. We will then see these methods in action by considering classical Markov chains for sampling proper graph colorings, configurations from the Ising model, and others.
José Correa and Andrés Cristi: Prophet inequalities
A prophet inequality refers to the existence of an online algorithm for a stochastic optimization problem whose outcome is, in expectation, close to that of a prophet, who can see the input in advance. The study of prophet inequalities has been very active since the classic work of Krengel and Sucheston, who established the single-item case. They proved that a gambler facing a finite sequence of non-negative independent random variables and who is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest. Following this classic theorem from the 70s, many results have been obtained for several related optimal stopping problems. Moreover, the recently uncovered connection between prophet inequalities and posted price mechanisms, has given the area a new surge. In this short course, we will cover not only some of the classic results in prophet inequalities but also new approaches and variants of the problem. These include data-driven approaches to prophet inequalities, combinatorial prophet inequalities, and online combinatorial auctions.
Yael Kalai: The Magic of Cryptography
In this mini course we will teach you two cryptographic magic tricks: The first is how to generate randomness out of thin air, and we will see how this trick can be used to construct secure encryption schemes (as well as other cryptographic primitives). The second is zero-knowledge proofs; like real magicians we will see how to prove statements without revealing any information (beyond the statement being true)!
Gillat Kol: Computability, Complexity, and Mathematical Logic – The Limits of Human Knowledge
Can any function be computed? Can every true mathematical statement be proven? Is solving a Sudoku Puzzle harder than verifying its solution? And why are we lucky to fail in solving some fundamental problems? In this mini-class we will take a computational lens, viewing real-life phenomena and entities, like our brains, evolution, and even black holes, as computational machines that run algorithms. We will ask what are the limits of computation and of efficient computation, and relate this to the study of proofs.
Andrea Lincoln: Why is Everything so Hard? Using Reductions to Explain the Difficulty of Solving Problems
Details to follow.