Yuancheng Yu

Yuancheng  Yu
MIT EECS Undergraduate Research and Innovation Scholar
Advisor: Erik D. Demaine
Department: EECS
Areas of Research: Theory of Computer Science
Years: 2017-2018
Research Project Title:

Extremal Distances in Directed Graphs

abstract:The diameter radius and node eccentricities of a graph are fundamental topological parameters that have many important practical applications in real world networks.For a-multiplicative B-additive approximations with expected "O ~(m^?)" time, there is a natural tradeoff between "a" and "?" Cairo et al proved lower bounds under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo et al, and upper bounds for undirected graphs. This project investigates the various techniques employed in relavant literature to generalize the results in Cairo et al to obtain new bounds for approximating extremal distances in directed graphs.

"I am intrigued by the elegance of combinatorial and algebraic algorithms, and I would like to investigate interesting open problems in the field."