{"id":18,"date":"2018-05-17T21:34:16","date_gmt":"2018-05-17T21:34:16","guid":{"rendered":"http:\/\/eventos.cmm.uchile.cl\/discretas2020\/?page_id=18"},"modified":"2022-01-11T19:44:24","modified_gmt":"2022-01-11T22:44:24","slug":"cursos","status":"publish","type":"page","link":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/cursos\/","title":{"rendered":"Cursos"},"content":{"rendered":"<p>Todos los cursos ser\u00e1n en ingl\u00e9s &#8211; <em>All courses will be given in English.<\/em><\/p>\n<div><\/div>\n<div>\n<h2>Graph Tur\u00e1n problems<\/h2>\n<p><a href=\"http:\/\/www.borisbukh.org\/\">Boris Bukh<\/a>, Carnegie Mellon University<br \/>\nTeaching assistant: Mat\u00edas Pavez-Sign\u00e9<\/p>\n<p><strong>Abstract:<\/strong> What is the largest number of edges in an n-vertex graph not<br \/>\ncontaining a fixed forbidden subgraph <em>F<\/em>? We begin with the classic<br \/>\nresult of Erd\u0151s and Stone that answers this question of Tur\u00e1n for<br \/>\nnon-bipartite <em>F<\/em> almost completely. We then discuss the main results for<br \/>\nthe bipartite case in detail, focusing on cycles and complete bipartite<br \/>\ngraphs. We shall explain both the embedding arguments that lead to the<br \/>\nupper bounds and various algebraic constructions that lead to the lower<br \/>\nbounds.<\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<div><\/div>\n<h2>Prophets, Secretaries, and other online puzzles<\/h2>\n<p><a href=\"https:\/\/www.cs.utexas.edu\/people\/faculty-researchers\/shuchi-chawla\">Shuchi Chawla<\/a>, University of Texas Austin<br \/>\nTeaching assistant: Andr\u00e9s Cristi<\/p>\n<p><strong>Abstract:<\/strong> In this course, we will introduce three online decision-making scenarios: the secretary problem, the prophet inequality, and the Pandora\u2019s 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.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h2>Submodular functions in combinatorial optimization<\/h2>\n<p><a href=\"https:\/\/theory.stanford.edu\/~jvondrak\/\">Jan Vondrak, <\/a>Stanford University<br \/>\nTeaching assistant: Boris Epstein<\/p>\n<p><strong>Abstract:<\/strong> 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\u00e1sz extension and the multilinear extension. Applications will include combinatorial auctions, Nash social welfare and streaming algorithms for big data.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Todos los cursos ser\u00e1n en ingl\u00e9s &#8211; All courses will be given in English. Graph Tur\u00e1n problems Boris Bukh, Carnegie Mellon University Teaching assistant: Mat\u00edas Pavez-Sign\u00e9 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\u0151s and Stone &hellip; <a href=\"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/cursos\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Cursos<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"inline_featured_image":false,"footnotes":""},"class_list":["post-18","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/pages\/18","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/comments?post=18"}],"version-history":[{"count":92,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/pages\/18\/revisions"}],"predecessor-version":[{"id":729,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/pages\/18\/revisions\/729"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2022\/wp-json\/wp\/v2\/media?parent=18"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}