- Time: 9:00-10:30am (Beijing), 10:00-11:30am(Seoul)
- Place: IBS ECOPRO B332 (Main building 3rd floor).
- Jul 28 – Aug 1, Around removal lemmas
- Aug 4 – 8, Introduction to Boolean analysis
- Zoom: 3469344087, PW: 2025
Around removal lemmas
Lior Gishboliner, University of Toronto, Canada
The removal lemma for a graph (or hypergraph) property $\mathcal{P}$ states that if a graph $G$ is $\varepsilon$-far from satisfying $\mathcal{P}$, then a random sample of $f(\varepsilon)$ vertices of $G$ is likely to not satisfy $\mathcal{P}$. Such results are useful both in combinatorics and theoretical computer science, where they correspond to property testing algorithms. Removal lemmas are typically proved using a regularity lemma, which leads to very poor bounds on $f(\varepsilon)$. A central problem is to understand for which properties $\mathcal{P}$ we can take $f(\varepsilon)$ to be polynomial in $\varepsilon$. The goal of this course is to give an overview of regularity and removal lemmas and present the tools used in the study of this question, including some recent results.
- 7/28 Lecture 1:
Introduction to Boolean analysis
Yuval Filmus, Technion, Israel
Boolean function analysis studies Boolean functions on the Boolean cube and other domains from a spectral perspective. Motivated initially by social choice theory, it has seen many applications in combinatorics and theoretical computer science. We will cover the basic definitions and results, and see some classical applications as well as some more recent ones.
- 8/4 Lecture 1: