Simpler Reductions from Exact Triangle

Timothy M. Chan, Yinzhan Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight 4-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight 4-cycles was considered by Jin and Xu [STOC 2023], who used it as an intermediate problem to show 3SUM hardness of All-Edges Sparse Triangle with few 4-cycles (independently obtained by Abboud, Bringmann and Fischer [STOC 2023]), which is further used to show 3SUM hardness of a variety of problems, including 4-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths and All-Nodes Shortest Cycles. We provide a simple reduction from Exact Triangle to Exact Triangle with few zero-weight 4-cycles. Our new reduction not only simplifies Jin and Xu’s previous reduction, but also strengthens the conditional lower bounds from being under the 3SUM hypothesis to the even more believable Exact Triangle hypothesis. As a result, all conditional lower bounds shown by Jin and Xu [STOC 2023] and by Abboud, Bringmann and Fischer [STOC 2023] using All-Edges Sparse Triangle with few 4-cycles as an intermediate problem now also hold under the Exact Triangle hypothesis. We also provide two alternative proofs of the conditional lower bound of the All-Edges Sparse Triangle problem under the Exact Triangle hypothesis, which was originally proved by Vassilevska Williams and Xu [FOCS 2020]. Both of our new reductions are simpler, and one of them is also deterministic—all previous reductions from Exact Triangle or 3SUM to All-Edges Sparse Triangle (including Pătraşcu’s seminal work [STOC 2010]) were randomized.

Original languageEnglish (US)
Title of host publication2024 Symposium on Simplicity in Algorithms, SOSA 2024
EditorsMerav Parter, Seth Pettie
PublisherSociety for Industrial and Applied Mathematics Publications
Pages28-38
Number of pages11
ISBN (Electronic)9781713887171
StatePublished - 2024
Externally publishedYes
Event7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024 - Alexandria, United States
Duration: Jan 8 2024Jan 10 2024

Publication series

Name2024 Symposium on Simplicity in Algorithms, SOSA 2024

Conference

Conference7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024
Country/TerritoryUnited States
CityAlexandria
Period1/8/241/10/24

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Simpler Reductions from Exact Triangle'. Together they form a unique fingerprint.

Cite this