Yuancheng  Yu

Yuancheng Yu

Scholar Title

MIT EECS Undergraduate Research and Innovation Scholar

Research Title

Extremal Distances in Directed Graphs





Research Areas
  • Theory of Computer Science

Erik D. Demaine


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.”

Back to Scholars