<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><h1 align="left" class=""><span style="font-size: 14pt; font-family: "Times New Roman", serif; font-weight: normal;" class="">The University of Chicago </span></h1><h1 align="left" class=""><span style="font-family: "Times New Roman", serif; font-size: 14pt; font-weight: normal;" class="">Department of Computer Science & Mathematics</span></h1><h1 align="left" class=""><span style="font-size: 14pt; font-family: "Times New Roman", serif; font-weight: normal;" class="">Combinatorics & Theoretical Seminar <o:p class=""></o:p></span></h1><div style="margin-left: 2in; text-indent: 0.5in;" class=""><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class=""> </span><br class="webkit-block-placeholder"></div><p class="MsoNormal"><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class="">Arturs Backurs</span><span style="font-size: 14pt;" class=""> (</span><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class="">TTIC)</span></p><p class="MsoNormal"><span style="font-family: "Times New Roman", serif; font-size: 14pt; text-align: center;" class="">Tuesday, November 13, 2018</span></p><p class="MsoNormal"><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class="">Ry. 251 @ 3:30 pm<o:p class=""></o:p></span></p><div style="text-align: justify;" class=""><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class=""> </span><br class="webkit-block-placeholder"></div><p class="MsoNormal" style="text-align: justify;"><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class="">Title: “Efficient Density Evaluation for Smooth Kernels”<o:p class=""></o:p></span></p><p class="MsoNormal" style="text-align: justify;"><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class="">Abstract:</span><span style="font-size: 14pt; font-family: "Times New Roman", serif; color: rgb(33, 33, 33); background-color: white; background-position: initial initial; background-repeat: initial initial;" class=""> </span><span style="font-size: 14pt; font-family: Arial, sans-serif;" class="">Given a kernel function k and a dataset P (of points from R^d), the kernel density function of P at a point q from R^d is equal to KDF_P(q) := 1/|P| sum_{p in P} k(p,q). Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate KDF_P(q) quickly, often for many inputs q and large point-sets P. In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is "smooth", i.e., the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after O(dn log(Phi n)/eps^2) preprocessing, estimates KDF_P(q) up to a factor of 1+eps in O(d log (Phi n)/eps^2) time, where Phi is the aspect ratio. The log(Phi n) term can be further replaced by log n under an additional decay condition on k, which is satisfied by the aforementioned examples. We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than l_2. The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain (1+eps)-approximate estimation algorithms for kernels over other l_p norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for l_p norms and other spaces. <o:p class=""></o:p></span></p><p class="MsoNormal"><span style="font-size: 14pt; font-family: Arial, sans-serif;" class="">Joint work with Moses Charikar, Piotr Indyk and Paris Siminelakis.<o:p class=""></o:p></span></p><div class=""><span style="font-size: 14pt;" class=""> </span><br class="webkit-block-placeholder"></div><p class="MsoNormal"><span style="font-size: 14pt; font-family: "Times New Roman", serif;" class=""> (Refreshments will be served prior to the talk in Ry. 255 @ 3:15pm)<o:p class=""></o:p></span></p><div class=""><span style="font-size: 14pt;" class=""> </span><br class="webkit-block-placeholder"></div><div class="">
<div style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-size: 11px;" class=""><br class="webkit-block-placeholder"></div><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""><p class="MsoNormal" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;"><br class=""></p></div></div></div></div></div></div></div></div></body></html>