STOC2023
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
4 citations
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.