Networks cannot compute their diameter in sublinear time.

Silvio Frischknecht, Stephan Holzer, Roger Wattenhofer

Browse the full SODA paper archive.