Todos los cursos serán en inglés – All courses will be given in English.
Graph Turán problems
Boris Bukh, Carnegie Mellon University
Teaching assistant: Matías Pavez-Signé
Abstract: What is the largest number of edges in an n-vertex graph not
containing a fixed forbidden subgraph F? We begin with the classic
result of Erdős and Stone that answers this question of Turán for
non-bipartite F almost completely. We then discuss the main results for
the bipartite case in detail, focusing on cycles and complete bipartite
graphs. We shall explain both the embedding arguments that lead to the
upper bounds and various algebraic constructions that lead to the lower
bounds.
Prophets, Secretaries, and other online puzzles
Shuchi Chawla, University of Texas Austin
Teaching assistant: Andrés Cristi
Abstract: In this course, we will introduce three online decision-making scenarios: the secretary problem, the prophet inequality, and the Pandora’s box problem. We will make connections between these problems and applications in economics and algorithm design. We will introduce a rich set of tools and techniques for solving various versions of these problems, as well as describe directions for future research.
Submodular functions in combinatorial optimization
Jan Vondrak, Stanford University
Teaching assistant: Boris Epstein
Abstract: We will discuss the concept of submodular functions, motivated by the notion of discrete convexity, and cover different techniques to deal with submodular functions in optimization problems: greedy, local search, the Lovász extension and the multilinear extension. Applications will include combinatorial auctions, Nash social welfare and streaming algorithms for big data.