Speaker:

Jie Xue(New York University Shanghai)

Time:

• 16:20-17:20 Beijing Time
• June 4, 2026 (Thursday)

Venue:

四号科研楼A区 518

Abstract:

Courcelle’s theorem is one of the most celebrated algorithmic meta-theorems and has brought a profound impact on the theory of parameterized complexity. The theorem states that every graph property expressible by a monadic second-order (MSO) formula ϕ can be checked in f(ϕ,t)·n time where n and t denote the number of vertices and the treewidth of the input graph, respectively. While the time complexity of Courcelle’s theorem is linear in n, the understanding of the function f(ϕ,t) in the bound remained poor and coarse. In this talk, we discuss a fine-grained version of Courcelle’s theorem with explicit dependence on the quantifier structure of ϕ and the treewidth parameter t, which is almost optimal assuming the ETH.

Speaker 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, Graph Theory, and Parameterized Complexity. 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.