{"id":289,"date":"2021-06-11T11:40:22","date_gmt":"2021-06-11T14:40:22","guid":{"rendered":"https:\/\/projects.cs.dal.ca\/wads2021\/?page_id=289"},"modified":"2021-06-24T09:48:09","modified_gmt":"2021-06-24T12:48:09","slug":"invited-speakers","status":"publish","type":"page","link":"https:\/\/projects.cs.dal.ca\/wads2021\/invited-speakers\/","title":{"rendered":"Invited Speakers"},"content":{"rendered":"\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-28f84493 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:33.33%\">\n<figure class=\"wp-block-image size-large border-image\"><img loading=\"lazy\" decoding=\"async\" width=\"840\" height=\"560\" src=\"https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/dujmovic.jpg\" alt=\"Vida Dujmovi\u0107\" class=\"wp-image-287\" srcset=\"https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/dujmovic.jpg 840w, https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/dujmovic-300x200.jpg 300w, https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/dujmovic-768x512.jpg 768w\" sizes=\"auto, (max-width: 840px) 100vw, 840px\" \/><\/figure>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:66.66%\">\n<h2 class=\"wp-block-heading\" style=\"font-size:24px\"><span class=\"has-inline-color has-vivid-purple-color\">Vida Dujmovi\u0107<\/span><\/h2>\n\n\n\n<h2 class=\"wp-block-heading\" style=\"font-size:24px\">Title: Adjacency Labelling of Planar Graphs<\/h2>\n\n\n\n<h2 class=\"wp-block-heading\" style=\"font-size:24px\">Abstract:<\/h2>\n\n\n\n<p>Adjacency labelling schemes, which have been studied since the 1980s, ask for short labels for n-vertex graphs G such that the labels of two vertices u and v are sufficient to determine (quickly) if uv is an edge of G. One of the long-standing problems in the area was the optimal length of labels for planar graphs. The problem is closely related to the size of the smallest universal graph for all n-vertex planar graphs. In this talk I will show how we resolved this problem (up to lower order terms) with the help of a new graph theoretic tool: a product-structure theorem for planar graphs. This new tool and our result are applicable not only to planar graphs but also to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.<\/p>\n<\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-28f84493 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:33.33%\">\n<figure class=\"wp-block-image size-large border-image\"><img loading=\"lazy\" decoding=\"async\" width=\"511\" height=\"481\" src=\"https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/ola.jpg\" alt=\"Ola Svensson \" class=\"wp-image-286\" srcset=\"https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/ola.jpg 511w, https:\/\/projects.cs.dal.ca\/wads2021\/wordpress\/wp-content\/uploads\/2021\/06\/ola-300x282.jpg 300w\" sizes=\"auto, (max-width: 511px) 100vw, 511px\" \/><\/figure>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:66.66%\">\n<h2 class=\"wp-block-heading\" style=\"font-size:24px\"><span class=\"has-inline-color has-vivid-purple-color\">Ola Svensson<\/span><\/h2>\n\n\n\n<h2 class=\"wp-block-heading\" style=\"font-size:24px\">Title: Algorithms for Explainable Clustering<\/h2>\n\n\n\n<h2 class=\"wp-block-heading\" style=\"font-size:24px\">Abstract: <\/h2>\n\n\n\n<p>An important topic in current machine learning research is to explain and\/or interpret how models actually make their decisions. Motivated by this, Moshkovitz, Dasgupta, Rashtchian, and Frost recently formalized the problem of explainable clustering. A k-clustering is said to be explainable if it is given by a decision tree where each internal node splits data points with a threshold cut in a single dimension (feature), and each of the k leaves corresponds to a cluster.<\/p>\n\n\n\n<p>In this talk, we see an algorithm that outputs an explainable clustering that loses at most a factor of O(log<sup>2<\/sup> k) compared to an optimal (not necessarily explainable) clustering for the k-medians objective, and a factor of O(k log<sup>2<\/sup> k) for the k-means objective. This improves over the previous best upper bounds of O(k) and O(k<sup>2<\/sup>), respectively, and nearly matches the previous \u03a9(log k) lower bound for k-medians and our new \u03a9(k) lower bound for k-means. Moreover, the algorithm is remarkably simple and, given an initial not necessarily explainable clustering, it is oblivious to the data points and runs in time O(dk log<sup>2<\/sup> k), independent of the number of data points n.<\/p>\n\n\n\n<p>This is joint work with Buddhima Gamlath, Xinrui Jia, and Adam Polak.<\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Vida Dujmovi\u0107 Title: Adjacency Labelling of Planar Graphs Abstract: Adjacency labelling schemes, which have been studied since the 1980s, ask for short labels for n-vertex graphs G such that the labels of two vertices u and v are sufficient to determine (quickly) if uv is an edge of G. One of the long-standing problems in [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"default","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-289","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/pages\/289","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/comments?post=289"}],"version-history":[{"count":24,"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/pages\/289\/revisions"}],"predecessor-version":[{"id":348,"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/pages\/289\/revisions\/348"}],"wp:attachment":[{"href":"https:\/\/projects.cs.dal.ca\/wads2021\/wp-json\/wp\/v2\/media?parent=289"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}