Abstract: One of the main themes of Theoretical Computer Science is to develop algorithms and data structures that can be theoretically proved to have good performances. Such algorithms are usually more effective, more robust, and hence more preferable than the ones without any theoretical guarantees. In this talk, I will discuss the research on designing (theoretical) algorithms for solving fundamental problems regarding geometric input and graph input. In particular, I will review some state-of-the-art results on this topic obtained by me and others.
Bio: Jie Xue is an Assistant Professor of Computer Science at NYU Shanghai. His research area is Theoretical Computer Science, and more specifically, Computational Geometry, Algorithms & Data Structures, and Graph Theory. His research mainly focuses on designing efficient algorithms and data structures for fundamental problems regarding geometric objects and graphs. His work has been published regularly on top venues of TCS, such as STOC, FOCS, SODA, SoCG, etc. and has received the Best Paper Award at SoCG’24 and a Distinguished Paper Award at AAAI’23.