Two notable success stories, highlighted in a recent survey by Rubinstein and Vassilevska Williams [1]}, are the Distributed PCP framework [2]} based on algebraic error-correcting codes that has lead to strong results for many pair-finding type of problems [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, and a graph-products technique [10]} that has lead to impressive inapproximability results for computing the diameter of a graph [11]}, [12]}, [13]}, [14]}, [15]}, [16]}.
Nevertheless, we are still far away from satisfactory results for many problems (see the open questions in [2]}, [1]}).
Even distance computations in graphs, an extensively studied subject in fine-grained complexity, exhibits many huge gaps.
