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/

Zendy Plus

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

Zendy Tools

Zendy Open

The $3$SUM hypothesis, the APSP hypothesis and SETH are the three mainhypotheses in fine-grained complexity. So far, within the area, the first twohypotheses have mainly been about integer inputs in the Word RAM model ofcomputation. The "Real APSP" and "Real $3$SUM" hypotheses, which assert thatthe APSP and $3$SUM hypotheses hold for real-valued inputs in a reasonableversion of the Real RAM model, are even more believable than their integercounterparts.  Under the very believable hypothesis that at least one of the Integer $3$SUMhypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. andYu [STOC 2015] showed that a problem called Triangle Collection requires$n^{3-o(1)}$ time on an $n$-node graph.  Our main result is a nontrivial lower bound for a slight generalization ofTriangle Collection, called All-Color-Pairs Triangle Collection, under the evenmore believable hypothesis that at least one of the Real $3$SUM, the Real APSP,and the OV hypotheses is true. Combined with slight modifications of priorreductions, we obtain polynomial conditional lower bounds for problems such asthe (static) ST-Max Flow problem and dynamic Max Flow, now under the new weakerhypothesis.  Our main result is built on the following two lines of reductions.  * Real APSP and Real $3$SUM hardness for the All-Edges Sparse Triangleproblem. Prior reductions only worked from the integer variants of theseproblems.  * Real APSP and OV hardness for a variant of the Boolean MatrixMultiplication problem.  Along the way we show that Triangle Collection is equivalent to a simplerrestricted version of the problem, simplifying prior work. Our techniques alsohave other interesting implications, such as a super-linear lower bound ofInteger All-Numbers $3$SUM based on the Real $3$SUM hypothesis, and a tightlower bound for a string matching problem based on the OV hypothesis.

Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV