New horizons in theoretical computer science

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)!