PaperlayerView exact revision on arXiv

Source-linked AI summary

Simpler Reductions from Exact Triangle

Timothy M. Chan, Yinzhan Xu

arXiv:2310.11575v1cs.DS

TL;DR

The paper seeks simpler reductions from Exact Triangle to problems used in conditional lower-bound proofs. It provides reductions to the few-zero-weight-4-cycles variant and All-Edges Sparse Triangle, strengthening some bounds and making one reduction deterministic.

  • Problem

    Earlier reductions to Exact Triangle with few zero-weight 4-cycles were technically involved, while the known Exact Triangle reduction to All-Edges Sparse Triangle was randomized.

    Source: §1 · p. 3

  • Method

    The paper gives a simpler Exact Triangle reduction to the few-zero-weight-4-cycles variant and two simpler reductions to All-Edges Sparse Triangle.

    Source: §1 · pp. 2–3

  • Results

    The few-zero-weight-4-cycles reduction upgrades several downstream bounds to the Exact Triangle hypothesis, and one All-Edges Sparse Triangle reduction is deterministic.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The bounds for 4-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths, and All-Nodes Shortest Cycles now hold under the Exact Triangle hypothesis.

    Source: §1 · p. 2

    The Sparse Triangle Detection bound requires the Strong Exact Triangle hypothesis; a nontrivial bound remains out of reach under the ordinary Exact Triangle hypothesis.

    Source: §4.1 · p. 10

Abstract

from arXiv · show

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 $3$SUM 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 $3$SUM 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 $3$SUM 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\u{a}tra\c{s}cu's seminal work [STOC 2010]) were randomized.

1 Introduction

The paper gives simpler reductions from Exact Triangle to two fine-grained problems, strengthening conditional lower bounds in the process. Its reduction to Exact Triangle with few zero-weight 4-cycles upgrades several downstream bounds from the 3SUM hypothesis to the Exact Triangle hypothesis.

1 Introduction

  • Exact Triangle asks whether an n-node graph with polynomially bounded integer edge weights contains a zero-weight triangle; its hypothesis follows if either the 3SUM or APSP hypothesis holds.The hypothesis states an n3−o(1) time lower bound for Exact Triangle in the Word-RAM model with O(log n)-bit words.Source: §1 · pp. 1–2
  • A two-page reduction from Exact Triangle to its few-zero-weight-4-cycles variant simplifies Jin and Xu’s technically involved approach and upgrades four downstream lower bounds to the Exact Triangle hypothesis.The upgraded bounds concern 4-Cycle Enumeration, Offline Approximate Distance Oracle, Dynamic Approximate Shortest Paths, and All-Nodes Shortest Cycles; the upgrade does not extend to Sidon Set Verification or 4-LDT.Source: §1 · p. 2
  • Two simpler reductions from Exact Triangle to All-Edges Sparse Triangle avoid hash functions; the first is deterministic and yields the same m4/3−o(1) conditional lower bound for that problem.The deterministic reduction also gives the first deterministic reduction from 3SUM to All-Edges Sparse Triangle; earlier reductions from Exact Triangle or 3SUM were randomized.Source: §1 · p. 3
  • The second reduction’s further consequences include an m5/4−o(1) Exact Triangle lower bound for All-Nodes Sparse Triangle and an m9/7−o(1) bound for Sparse Triangle Detection under a balanced bounded-weight Exact Triangle hypothesis.Sparse Triangle Detection’s bound uses the balanced bounded-weight variant, not the ordinary Exact Triangle hypothesis.Source: §1 · pp. 3–4

2 Exact Triangle with Few Zero-Weight 4-Cycles

The paper gives a simpler reduction to Exact Triangle instances with Property 2.1, strengthening the conditional lower bound from the 3SUM hypothesis to the Exact Triangle hypothesis. Its proof handles instances with few and many zero-weight 4-cycles by different methods.

2 Exact Triangle with Few Zero-Weight 4-Cycles

  • Property 2.1 uses directed edge weights, requires antisymmetry, and limits zero-weight 4-cycles to n^3, including cycles with repeated vertices.For a triangle (i, j, k), its weight is w_ij + w_jk + w_ki.Source: §2 · p. 4
  • The reduction simplifies Jin and Xu’s [JX23] long proof and establishes the property’s lower bound under the Exact Triangle hypothesis rather than 3SUM.Jin and Xu’s result was under the 3SUM hypothesis.Source: §2 · p. 4
  • Under the Exact Triangle hypothesis, Exact Triangle instances with Property 2.1 require n^3−o(1) time.A faster algorithm would yield a truly subcubic algorithm for Exact Triangle.Source: §2 · pp. 4–5
  • When there are at most n^4−δ zero-weight 4-cycles, random vertex partitioning creates O(n^3−3x) instances of O(nx) nodes while preserving zero-weight triangles.Sampling estimates distinct-vertex zero-weight 4-cycles up to n^2x additive error with high probability; instances with large estimates are solved by brute force.Source: §2 · pp. 4–5
  • When there are more than Ω(n^4−δ) cycles, the proof finds a pair in many such cycles and uses Equality Product to test and remove a large edge subset.The subset E0 has size Ω(n^2−δ) with high probability; after removing it, the procedure iterates on the remaining graph.Source: §2 · p. 5
  • The two cases yield a truly subcubic algorithm if Property 2.1 instances had a faster-than-cubic algorithm, contradicting the Exact Triangle hypothesis.The dense-cycle case is called at most O(n^δ) expected times, while the sparse-cycle case is called at most once.Source: §2 · p. 5

3 All-Edges Sparse Triangle: First Alternative Proof

The paper gives a deterministic, hash-free alternative reduction from Exact Triangle to All-Edges Sparse Triangle. Under the Exact Triangle hypothesis, this yields the m^4/3−o(1) conditional lower bound for All-Edges Sparse Triangle.

3 All-Edges Sparse Triangle: First Alternative Proof

  • This alternative proof adapts Chan, Vassilevska Williams, and Xu’s [CVX22] reduction, halves weights recursively, and is deterministic and hash-free.The paper presents it as an alternative proof of the lower bound originally proved by Vassilevska Williams and Xu [VX20].Source: §3 · p. 6
  • Under the Exact Triangle hypothesis, All-Edges Sparse Triangle requires m^4/3−o(1) time.A faster algorithm would imply a truly subcubic algorithm for Exact Triangle.Source: §3 · pp. 6–7
  • The proof assumes a tripartite Exact-Triangle instance with |A|=|B|=n and |C|=√n, and studies finding, for every (a,b)∈A×B, c_ab∈C with |w_ab+w_b,c_ab+w_a,c_ab|≤3, if one exists.This stronger version is equivalent to finding zero-weight triangles after multiplying all initial edge weights by 4.Source: §3 · p. 6
  • At each recursion level, weights are halved; pair groups indexed by the recursive candidate and weight sum are split, as are the subsets of C used in the constructed instances.The base case has weights in [±O(1)] and is solved in eO(n^ω) time.Source: §3 · p. 6
  • For each group, weight offset, and C subset, a sparse-triangle instance encodes candidate edges, and detecting a triangle identifies a candidate for the original pair.The construction uses copies of A and B and a sparsely represented vertex set based on C_s.Source: §3 · pp. 6–7

4 All-Edges Sparse Triangle: Second Alternative Proof

This proof reduces Exact Triangle Listing to Sparse Triangle Listing, then uses hashing to obtain the All-Edges Sparse Triangle lower bound under the Exact Triangle hypothesis. The discussion derives further lower bounds for All-Nodes Sparse Triangle and Sparse Triangle Detection, with different hypothesis and randomization requirements.

4 All-Edges Sparse Triangle: Second Alternative Proof

  • The second alternative proof is based on an idea from Jin and Xu’s Sparse Triangle Detection lower bound.Source: §4 · p. 7
  • Exact Triangle Listing reduces to Sparse Triangle Listing on graphs with O(n^2W^1/3) edges by encoding each weight in three coordinates and lifting vertices.The construction preserves zero-sum triangles, so listing triangles in the new graph solves the original listing problem.Source: §4 · pp. 7–8
  • A random-prime reduction converts Exact Triangle detection into listing triangles whose weights are 0 modulo p, with O(t log n) expected nonzero-weight false positives.If listing exceeds its time allowance, the process can infer a yes answer with constant probability, or with high probability after logarithmic repetition.Source: §4 · p. 8
  • Under the Exact Triangle hypothesis, All-Edges Sparse Triangle requires m^4/3−o(1) time.Source: §4 · p. 8

4.1 Discussion and Further Consequences

  • The All-Edges Sparse Triangle proof uses Monte Carlo randomization; the authors say full derandomization without slowdown is unclear, while Section 3 gives a deterministic alternative.Source: §4.1 · p. 9
  • Under the Exact Triangle hypothesis, All-Nodes Sparse Triangle requires m^5/4−o(1) time.The argument combines reductions through bounded-degree Sparse Triangle Listing and All-Nodes Sparse Triangle.Source: §4.1 · pp. 9–10
  • Under the Strong Exact Triangle hypothesis, Sparse Triangle Detection requires m^9/7−o(1) time.The paper notes this balanced-case assumption differs from the unbalanced hypothesis used for an earlier lower bound.Source: §4.1 · p. 10
  • For tripartite Exact Triangle detection, the reduction gives a bound parameterized by three part sizes and weight range, rather than only the balanced bound used in prior work.The discussion contrasts this general bound with the All-Edges Sparse Triangle proof’s slightly stronger exponent in its stated setting.Source: §4.1 · pp. 9–10

A A Simple Reduction from 3SUM to Sparse Triangle Listing

This appendix gives a simpler, more symmetric reduction from 3SUM to Sparse Triangle Listing. It proves the All-Edges Sparse Triangle lower bound under the 3SUM hypothesis and also describes a direct deterministic route that avoids hashing.

A A Simple Reduction from 3SUM to Sparse Triangle Listing

  • The appendix presents the proof as simpler and more symmetric than earlier reductions, with potential pedagogical value.It compares the proof with P˘atra¸scu’s and Kopelowitz, Pettie and Porat’s reductions.Source: A A Simple Reduction from 3SUM to… · p. 12
  • For numbers in [±W], 3SUM-LIST(n, t | W) reduces to O(1) instances of SPARSE-TRI-LIST(nW^(1/3), t), where q = W^(1/3).The reduction constructs an unweighted tripartite graph whose three node partitions are each indexed by [±q]^2.Source: A A Simple Reduction from 3SUM to… · pp. 12–13
  • Under the 3SUM hypothesis, All-Edges Sparse Triangle requires m^4/3−o(1) time.Source: A A Simple Reduction from 3SUM to… · p. 13
  • A direct deterministic reduction from 3SUM to All-Edges Sparse Triangle can combine weight halving with a reduction to #All-Edges Sparse Triangle, avoiding hashing.The alternative route through Convolution-3SUM and Exact Triangle would require hashing in its 3SUM-to-Convolution-3SUM stage, though that stage has been derandomized.Source: A A Simple Reduction from 3SUM to… · p. 13
Loading 2310.11575v1…