Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

by Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

Oded's comments

Rather than highlighting (in the title) a common technical aspect of the proofs, I would have highlighted (as done in the introduction) a common conceptual theme of the results. Specifically, the results address questions regarding the sensitivity of (fine-grained) complexity to variants such as directed vs undirected, fixed order vs none, and counting vs deciding. More specifically, the results include

The original abstract

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou?ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity:

See arxiv 2303.14572.

Back to list of Oded's choices.