Conference PaperMessage Optimality and Message-Time Trade-offs for APSP and BeyondDufoulon, Fabien [School of Computing and Communications, Lancaster University, Lancaster, United Kingdom] (ORCID:0000000329774109); Pai, Shreyas [IIT Madras, Chennai, India] (ORCID:0000000324097807); Pandurangan, Gopal [Department of Computer Science, University of Houston, Houston, Texas, USA] (ORCID:0000000158336592); Pemmaraju, Sriram [University of Iowa, Iowa City, Iowa, USA] (ORCID:0000000208343476); Robinson, Peter [Augusta University, Augusta, Georgia, USA] (ORCID:0000000274427002)Not AvailableACM2025-06-1310677725299 to 3099798400718854https://doi.org/10.1145/3732772.37335062402835National Science Foundation