In a connected, weighted, and undirected graph, a minimum spanning tree is defined as the spanning tree with the minimum total cost of all. There have been a number of different algorithms to find the minimum spanning tree, and scientists are still seeking to improve the efficiency. Intuitively, finding the MST should only require a linear number of edge weight comparisons, and all known algorithms are doing extra work by introducing unnecessary comparisons. The Minimum Spanning Tree problem asks whether there exists a deterministic linear time algorithm to find MST. Its a fundamental problem of interest in network algorithms, and wed like to find out the solution.

I have worked with Prof. Henry Cohn on the Kissing Number Problem. I worked with Prof. Dana Moshkovitz this spring/summer on the Minimum Spanning Tree Problem.