Zixuan Xu

Zixuan  Xu
Undergraduate Research and Innovation Scholar
Advisor: Virginia Williams
Department: Mathematics
Areas of Research: Theory of Computer Systems
Years: 2020-2021
Research Project Title:

Improving Distance Preservers and Additive Spanners

abstract:Let G be a graph on n vertices, a sparse subgraph H of G is called a spanner of G if it preserves the pairwise distances in G up to some bounded error. Coppersmith and Elkin introduced and studied the notion of pairwise and sourcewise distance preservers, which are another version of graph spanners where some of the pairwise distances are preserved exactly. In particular, they used techniques in discrete geometry and combinatorial graph theory that lower bound and upper bound the size of distance preservers. This project aims to work towards closing the gap between the current bounds and construct better distance preservers.

I am participating in SuperUROP because I want to gain research experience in combinatorial algorithms. I am interested in applying techniques in combinatorial graph theory to problems in theoretical computer science.