时间：9月23日 10:00-11:30

地点：立德楼1826报告厅

邀请人：魏哲巍 中国人民大学高瓴人工智能学院教授

主讲人：甘骏豪 墨尔本大学 Senior Lecturer

报告题目：Exact And Optimal Dynamic Parameterized Subset Sampling on Bounded Precision Machines

报告摘要：In this talk, I will present our recent work on the problem of Dynamic Parameterized Subset Sampling (DPSS) in the Word RAM model. In DPSS, the input is a set, S, of n items, where each item, x, has a non-negative integer weight, w(x). Given a pair of query parameters, (\alpha, \beta), each of which is a non-negative rational number, a parameterized subset sampling query on S seeks to return a subset T of S such that each item x from S is selected in T, independently, with probability p_x which is the minimum between w(x) / (\alpha W + \beta) and 1, where W is the sum of the weights of all the items in S. Moreover, in the DPSS problem, the item set, S, can be updated with insertions of new items or deletions of existing items.

Our first main result is an optimal algorithm for solving the DPSS problem.

Our second result is a hardness result for the DPSS problem when the item weights are O(1)-word float numbers, rather than integers. We show that an optimal deletion-only algorithm for DPSS with float item weights implies an optimal algorithm for Integer Sorting, while the latter still remains an important open problem.Last but not least, we show exact and efficient algorithms for the generation of two special types of Bernoulli random variates and the Truncated Geometric random variates in the Word RAM model, which are crucial components in our optimal DPSS algorithm.

嘉宾简介：Junhao Gan is a senior lecturer in School of Computing and Information Systems (CIS) at The University of Melbourne (UoM). Before joining the UoM, he was a post-doctoral research fellow in School of Information Technology and Electrical Engineering (ITEE) at The University of Queensland (UQ) from April 2017 to July 2018. He received his PhD degree proudly under the supervision of Prof. Yufei Tao in the same school at UQ in 2017, and obtained his bachelor and master degrees at Sun Yat-Sen University in 2011 and 2013, respectively. Junhao’s research interests are practical algorithms with non-trivial theoretical guarantees for solving problems on massive data. He is a recipient of the Discovery Early Career Researcher Award (DECRA), the 2015 SIGMOD Best Paper Award, and the Australasian Distinguished Doctoral Dissertation Award.