Zixuan  Xu

Zixuan Xu

Scholar Title

Undergraduate Research and Innovation Scholar

Research Title

Improving Distance Preservers and Additive Spanners





Research Areas
  • Theory of Computer Systems

Virginia Williams


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.

Back to Scholars