English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we carefully combine Fredman's trick [SICOMP'76] andMatou\v{s}ek's approach for dominance product [IPL'91] to obtain powerfulresults in fine-grained complexity:  - Under the hypothesis that APSP for undirected graphs with edge weights in$\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $\omega=2$), we show avariety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower boundfor unweighted directed APSP and an $n^{2.2-o(1)}$ lower bound for computingthe Minimum Witness Product between two $n \times n$ Boolean matrices, even if$\omega=2$, improving upon their trivial $n^2$ lower bounds. Our techniques canalso be used to reduce the unweighted directed APSP problem to other problems.In particular, we show that (when $\omega = 2$), if unweighted directed APSPrequires $n^{2.5-o(1)}$ time, then Minimum Witness Product requires$n^{7/3-o(1)}$ time.  - We show that, surprisingly, many central problems in fine-grainedcomplexity are equivalent to their natural counting versions. In particular, weshow that Min-Plus Product and Exact Triangle are subcubically equivalent totheir counting versions, and 3SUM is subquadratically equivalent to itscounting version.  - We obtain new algorithms using new variants of the Balog-Szemer\'edi-Gowerstheorem from additive combinatorics. For example, we get an $O(n^{3.83})$ timedeterministic algorithm for exactly counting the number of shortest paths in anarbitrary weighted graph, improving the textbook $\widetilde{O}(n^{4})$ timealgorithm. We also get faster algorithms for 3SUM in preprocessed universes,and deterministic algorithms for 3SUM on monotone sets in $\{1, 2, \ldots,n\}^d$.

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