{"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":"2023-01-15T22:29:26","modified_gmt":"2023-01-15T22:29:26","slug":"cursos","status":"publish","type":"page","link":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/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

Graphs with high chromatic number.<\/span><\/strong><\/h5>\n

Marthe Bonamy<\/strong><\/em><\/span><\/strong><\/p>\n

TA: Antonia Labarca<\/p>\n

\n
\n
Chromatic number is one of the most studied and least understood parameter in graph theory, both from the structural and the algorithmic point of view. Given a 3-colorable graph G on n vertices, but without access to a 3-colouring of it, the best known polynomial algorithm computes a ~n0.2<\/sup><\/var>-colouring. However, there is no theoretical guarantee that n0.2<\/sup><\/var> is best here — for all we know it could be replaced with log n.

This algorithmic failure reflects the (structural) fact that graphs with high chromatic number can be extremely simple on a small scale — for example, they can “look like a tree” around every vertex. To construct such objects, Erd\u0151s developed the so-called probabilistic method, which proved to be useful for a wide range of graph-theoretic problems. However, the difficulty (and beauty) of chromatic number is that constructions of locally simple\/globally hard graphs also arise from other areas: for instance the Borsuk-Ulam theorem directly provides graphs with high chromatic number in which all small subgraphs are bipartite (2-colorable).

This question “What makes the chromatic number large?” has several starkly different answers and seems to be very difficult. Ideally, we would like to tie this elusive parameter to other tamer parameters, like the maximum degree, even to some that are still hard to compute but present a local structure, like the maximum size of a clique (clique number). This is impossible in general, but we investigate specific graph classes, such as perfect graphs or minor closed classes (e.g. planar), where it can be tied to a parameter or another.

In this course, we will keep an eye on both structural results and (sometimes!) efficient algorithms.<\/div>\n<\/div>\n<\/div>\n
<\/h5>\n
Provable Algorithms for Data Mining and Machine Learning.<\/span><\/strong><\/h5>\n

Vincent Cohen-Addad<\/strong><\/em><\/span><\/strong><\/p>\n

TA: Benjam\u00edn Jauregui<\/p>\n

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

Data mining and machine learning tools are at the heart of large number of computer science applications, in both academic and industrial worlds. Thus, designing efficient and scalable algorithms for problems arising in these contexts is a central research question. In this course, we will present algorithms with provable guarantees for several of these applications (e.g.: clustering), and in several contexts (e.g.: differential-privacy).<\/p>\n

<\/h5>\n
Linear programming: the quest for strongly polynomial algorithms.
\n<\/span><\/strong><\/h5>\n

Laszlo Vegh<\/strong><\/em><\/span><\/strong><\/p>\n

\n
\n

TA: Arturo Merino<\/p>\n

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

\n
\n

Breakthrough results in the 1980s led to the first polynomial-time algorithms for linear programming: the ellipsoid and interior point methods. However, the running time of these algorithms depends on the bit-complexity of the input. It remains a major open problem to find a strongly polynomial algorithm, where the running time only depends on the number of variables and constraints.<\/p>\n<\/div>\n<\/div>\n

\n
\n

Such algorithms are known for various network optimization problems. For general linear programs, the best known bounds depend on certain condition numbers of the constraint matrix.<\/p>\n<\/div>\n

The lectures will give an overview of classical and recent results and techniques for strongly polynomial computability. These include proximity results, as well as a special class of combinatorial interior point methods.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Todos los cursos ser\u00e1n en ingl\u00e9s \u2013 All courses will be given in English. Graphs with high chromatic number. Marthe Bonamy TA: Antonia Labarca Chromatic number is one of the most studied and least understood parameter in graph theory, both from the structural and the algorithmic point of view. Given a 3-colorable graph G on … Contin\u00fae 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\/discretas2023\/wp-json\/wp\/v2\/pages\/36","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/users\/55"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/comments?post=36"}],"version-history":[{"count":9,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/pages\/36\/revisions"}],"predecessor-version":[{"id":152,"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/pages\/36\/revisions\/152"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/discretas2023\/wp-json\/wp\/v2\/media?parent=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}