Trying to answer the above questions negatively by a lower bound leads to a common barrier; it is the short cycle barrier discussed below.
Overcoming this barrier is related to Open Question 5 in the distributed PCP paper [1]} asking for gap amplification techniques from conjectures other than SETH.
This is because (the exact versions of) our distance computation problems are not SETH-hard; their hardness is via reductions from (detecting or) listing triangles in a graph, a problem that is hard under the 3SUM or APSP conjectures, but not under SETH.
