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.