{"id":36,"date":"2022-07-19T16:19:42","date_gmt":"2022-07-19T16:19:42","guid":{"rendered":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/?page_id=36"},"modified":"2025-11-25T16:50:01","modified_gmt":"2025-11-25T19:50:01","slug":"cursos","status":"publish","type":"page","link":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/cursos\/","title":{"rendered":"Cursos"},"content":{"rendered":"

Todos los cursos ser\u00e1n en ingl\u00e9s \u2013 All courses will be given in English.<\/em><\/p>\n

Course 1: Sketching Algorithms<\/strong><\/h2>\n

Lecturer: Jelani Nelson<\/strong><\/em>
\nTeaching Assistant: TBD<\/p>\n

Abstract:<\/strong><\/p>\n

A \u00absketch\u00bb 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 \u00abstreaming algorithm\u00bb 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.<\/div>\n
<\/div>\n
Ir arriba<\/a><\/div>\n

Course 2:\u00a0Hadwiger\u2019s Conjecture<\/strong><\/h2>\n

Lecturer: Zi-Xia Song<\/strong><\/em>
\nTeaching Assistants: TBD<\/p>\n

Abstract:<\/strong>
\nHadwiger\u2019s Conjecture from 1943 states that for every integer t\u00a0\u2265\u00a01<\/span>, every graph with no Kt<\/sub><\/span> minor is (t\u00a0\u2212\u00a01)<\/span>-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<\/sub><\/span> minor is O(t(log\u00a0t)1\/2<\/sup>)<\/span>, obtained independently by Kostochka and Thomason in 1984, while joint with Norin and Postle, we improved the frightening (log\u00a0t)1\/2<\/sup><\/span> term to (log\u00a0t)1\/4<\/sup> <\/span> in 2019. The current record, O(t\u00a0log\u00a0log\u00a0t)<\/span>, is due to Delcourt and Postle. In this short course we will survey the history of Hadwiger\u2019s Conjecture and discuss the main ideas of our results. We will also discuss our recent results on two strengthening of the conjecture: Odd Hadwiger\u2019s Conjecture and Dominating Hadwiger\u2019s conjecture.<\/p>\n

Ir arriba<\/a><\/div>\n

Course 3: Topics in Algorithmic Decision Making Under Uncertainty<\/strong><\/h2>\n

Lecturer: Shaddin Dughmi<\/strong><\/em>
\nTeaching Assistants: TBD<\/p>\n

Abstract:\u00a0<\/strong>
\nThis 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.\u00a0 There are also settings \u00a0where 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.<\/p>\n

Ir arriba<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"

Todos los cursos ser\u00e1n en ingl\u00e9s \u2013 All courses will be given in English. Course 1: Sketching Algorithms Lecturer: Jelani Nelson Teaching Assistant: TBD Abstract: A \u00absketch\u00bb 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 … Seguir leyendo Cursos<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":55,"featured_media":0,"parent":0,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"inline_featured_image":false,"footnotes":""},"class_list":["post-36","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/pages\/36","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/users\/55"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/comments?post=36"}],"version-history":[{"count":43,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/pages\/36\/revisions"}],"predecessor-version":[{"id":556,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/pages\/36\/revisions\/556"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2026\/wp-json\/wp\/v2\/media?parent=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}