Cursos

Todos los cursos serán en inglés – All courses will be given in English.

Course 1: Sketching Algorithms

Lecturer: Jelani Nelson
Teaching Assistant: TBD

Abstract:

A «sketch» is a data structure supporting some pre-specified set of queries and updates to a database while consuming space substantially (often exponentially) less than the information theoretic minimum required to store everything seen, and thus can also be seen as some form of functional compression. A «streaming algorithm» is simply a data structure that maintains a sketch dynamically as data is updated. The advantages of sketching include less memory consumption, faster algorithms, and reduced bandwidth requirements in distributed computing environments. Despite decades of work in the area, some of the most basic questions still remain open or were only resolved recently. In this course, I cover some core streaming topics and also survey the research frontier.
Ir arriba

Course 2: Hadwiger’s Conjecture

Lecturer: Zi-Xia Song
Teaching Assistants: TBD

Abstract:
Hadwiger’s Conjecture from 1943 states that for every integer t ≥ 1, every graph with no Kt minor is (t − 1)-colorable. This is a far-reaching generalization of the Four-Color Theorem and perhaps the most famous conjecture in graph theory. Until recently the best known upper bound on the chromatic number of graphs with no Kt minor is O(t(log t)1/2), obtained independently by Kostochka and Thomason in 1984, while joint with Norin and Postle, we improved the frightening (log t)1/2 term to (log t)1/4 in 2019. The current record, O(t log log t), is due to Delcourt and Postle. In this short course we will survey the history of Hadwiger’s Conjecture and discuss the main ideas of our results. We will also discuss our recent results on two strengthening of the conjecture: Odd Hadwiger’s Conjecture and Dominating Hadwiger’s conjecture.

Ir arriba

Course 3: Topics in Algorithmic Decision Making Under Uncertainty

Lecturer: Shaddin Dughmi
Teaching Assistants: TBD

Abstract: 
This course will survey some of the central models and approaches for algorithmic decision making in the presence of uncertainty. Many such problems feature information that arrives gradually over time, and irrevocable decisions that must be made along the way. Here, the decision-maker’s algorithm must hedge against an uncertain future.  There are also settings  where information must be actively acquired prior to decision making. Acquiring information can be costly or constrained, necessitating decisions on which information is most pertinent. Topics will include secretary problems, prophet inequalities, stochastic probing problems, and in particular their generalizations to multivariate combinatorial optimization settings.

Ir arriba