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 | Antonio Blanca | Nicole Immorlica |
| Tuesday | Antonio Blanca | Yael Kalai |
| Wednesday | Ashia Wilson | Nicole Immorlica |
| Thursday | Yael Kalai | Jelani Nelson |
| Friday | Ashia Wilson | Jelani Nelson |
Ashia Wilson: Algorithms for Machine Learning
Machine learning algorithms sculpt many people’s social lives. They mediate our exposure to information – which advertisements and reports of the world we see – and they mediate our access to institutional resources – including hiring, financial, healthcare, and educational resources. Optimization lies at the core of machine learning as well as other fields concerned with data analysis. It provides a mathematical language in which both computational and statistical concepts can be expressed and it delivers practical data analysis algorithms that can scale to the enormous datasets that are increasingly the norm in science and technology. This mini course will explore basic principles for designing optimization algorithms for machine learning as well as frameworks for thinking through machine learning’s societal impacts.
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 that converges to a desired distribution. A fundamental research question in theoretical computer science, discrete mathematics, and other more applied areas, is how many steps of the 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 probabilistic and analytical methods for bounding the speed of convergence. We will then focus on the coupling method, the most standard probabilistic technique for analyzing convergence rates, and some of its statistical physics applications. In particular, we will use the coupling method for analyzing Markov chains for sampling proper colorings of a graph and configurations from the Ising model.
Jelani Nelson: Streaming Algorithms
Streaming’ algorithms make just one pass over a data stream then are able to answer queries, while using memory much less than what would be required to store the full stream. In these lectures we will show how to design and analyze some of the most popularly used streaming algorithms.
Nicole Immorlica: Market Design
Markets determine who gets what. A labor market determines who gets what job. A school choice market determines who goes to which school. A kidney exchange market determines who gets a kidney transplant, and from which donor. In this course, we will explore desirable market outcomes and how to achieve them using algorithms.
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)!