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

Chan, TM; Williams, VV; Xu, YZ

Chan, TM (通讯作者),UIUC, Champaign, IL 61820 USA.

PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023; (): 419

Abstract

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matousek's approach for dominance product [IPL'91] to obtain powerful results in fi......

Full Text Link