Recent Advances on Geometric Streaming Algorithms

演讲人: Shaofeng Jiang Peking University
时间: 2024-06-11 15:00-2024-06-11 16:00
地点:FIT 1-222

Geometric streaming algorithms aim to find approximation for geometric optimization problems over a point stream in R^d, using small space. There has been flourish research on the low dimensional case (where typically d = O(1)), while the case of high dimension is much less understood.
In this talk, we will discuss recent advances on geometric streaming algorithms, particularly in high dimension. Besides summarizing the results, we will focus on introducing the techniques developed around this line of research, including geometric hashing and new regimes of dimensionality reduction.
We will conclude with future directions and open questions.


Shaofeng Jiang is currently an assistant professor at Peking University. Before he joined PKU, he has worked as an assistant professor at Aalto University and as a postdoc at Weizmann Institute of Science. He obtained PhD from University of Hong Kong. His research interest lies in theoretical computer science, with a focus on algorithms, especially sublinear algorithms, approximation algorithms and online algorithms.