Todos los cursos serán en inglés – All the courses will be given in english.
“Approximation Algorithms for Stochastic Combinatorial Optimization”
Anupam Gupta, Carnegie Melon University, USA.
Teaching assistant: Andrés Cristi y Arturo Merino.
Abstract: In this set of lectures I will survey some ways to model combinatorial optimization problems in the presence of uncertain inputs. These problems are typically NP-hard (or worse), and I will discuss techniques used to develop approximation algorithms for these kinds of problems. Examples include two-stage and multi-stage optimization, stochastic packing and scheduling problems, and stochastic problems in online settings where irrevocable decisions are made on-the-fly.
“Introduction to Differential Privacy”
Katrina Ligett, Hebrew University, Israel.
Teaching assistant: Sebastián Pérez.
Abstract: This short course will motivate and introduce the notion of differential privacy. Students will be exposed to basic differentially private algorithms and key ideas involved in analyzing them. The course will also briefly explore the limitations of the notion and the art of developing new mathematical models for social phenomena. The course requires mathematical maturity, particularly in probabilistic and algorithmic thinking.
References:
- The course will cover elements of the textbook by Dwork and Roth, available for free download here: The Algorithmic Foundations of Differential Privacy
“The method of hypergraph containers”
Rob Morris, IMPA, Brazil.
Teaching assistant: Matías Pavez-Signé.
Abstract: In this course, we will discuss a technique, introduced in [BMS] and [ST], that has proved to be extremely useful in the study of problems of the following types:
- Counting objects with forbidden substructures.
- Proving extremal results in random objects.
- Determining the `typical’ structure of sparse objects.
- Constructing counter-intuitive objects (usually randomly).
This technique is based on a subtle `clustering’ phenomenon exhibited by the independent sets of k-uniform hypergraphs whose edges are sufficiently evenly distributed; more precisely, it provides a relatively small family of sparse `containers’ for the independent sets.
In order to illustrate the method, we will consider the number of C4-free graphs, the typical structure of a Kr-free graph, and the maximum number of edges in an H-free subgraph of G(n,p). I also hope to discuss some recent developments, including the `efficient’ and `asymmetric’ versions, and applications to additive combinatorics and discrete geometry.
References:
- [BMS] J. Balogh, R. Morris and W. Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc. 28:669-709 (2015).
- [BMS18] J. Balogh, R. Morris and W. Samotij, The method of hypergraph containers, Proc. Int. Cong. Math., Rio de Janeiro, 3:3045-3078 (2018).
- [BSa] J. Balogh and W. Samotij, An efficient container lemma, arXiv:1910.09208.
- [BSo] J. Balogh and J. Solymosi, On the number of points in general position in the plane, Discrete Analysis 16, 20pp (2018).
- [Ca] M. Campos, On the number of sets with a given doubling constant, Israel J. Math. 236:711-726 (2020).
- [CCMMS] M. Campos, M. Collares, R. Morris, N. Morrison and V. Souza, The typical structure of sets with small sumset, arXiv:1910.11324
- [FMS] A. Ferber, G. McKinley, and W. Samotij, Supersaturated sparse graphs and hypergraphs, Int. Math. Res. Notices 378-402 (2020).
- [MSS] R. Morris, W. Samotij, and D. Saxton, An asymmetric container lemma and the structure of graphs with no induced 4-cycle, arXiv:1806.03706.
- [ST] D. Saxton and A. Thomason, Hypergraph containers, Inventiones Math. 201:1-68 (2015).