SCIENCE@home

3SUM, 3XOR, Triangles

Zahra Jafargholi,Emanuele Viola

Published 2013 in Electron. Colloquium Comput. Complex.

ABSTRACT

We show that if one can solve 3SUM on a set of size n in time n^{1+\e} then one can list t triangles in a graph with m edges in time O(m^{1+\e}t^{1/3-\e/3}). This is a reversal of Patrascu's reduction from 3SUM to listing triangles (STOC '10). Our result builds on and extends works by the Paghs (PODS '06) and by Vassilevska and Williams (FOCS '10). We make our reductions deterministic using tools from pseudorandomness. We then re-execute both Patrascu's reduction and our reversal for the variant 3XOR of 3SUM where integer summation is replaced by bit-wise xor. As a corollary we obtain that if 3XOR is solvable in linear time but 3SUM requires quadratic randomized time, or vice versa, then the randomized time complexity of listing m triangles in a graph with $m$ edges is m^{4/3} up to a factor m^\alpha for any \alpha > 0.

PUBLICATION RECORD

  • Publication year

    2013

  • Venue

    Electron. Colloquium Comput. Complex.

  • Publication date

    2013-05-16

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1305.3827
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-26 of 26 references · Page 1 of 1

CITED BY

Showing 1-37 of 37 citing papers · Page 1 of 1