Antoine Vigneron, A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space

A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space
Antoine Vigneron
KAUST, Kingdom of Saudi Arabia
2014/03/31 Monday 4PM-5PM
Room 1409
We show that the Gromov hyperbolicity of a discrete metric space at a fixed base-point cannot be computed in O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication algorithm than is currently known.

Tags:

This entry was posted on Tuesday, February 25th, 2014 at 5:30 pm and is filed under 2014, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.