Matching triangles and basing hardness on an extremely popular conjecture

Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu

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

59 Scopus citations

Abstract

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining "less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including: • Tight n3-o(1) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs. • New n1-o(1) lower bounds for the amortized update and query times of dynamic algorithms for single-source reachability, strongly connected components, and Max-Flow. • New n1.5-o(1) lower bound for computing a set of n st-maximum-flow values in a directed graph with n nodes and Õ(n) edges. • There is a hierarchy of natural graph problems on n nodes with complexity nc for c ∈ (2,3). Only slightly non-trivial consequences of this conjecture were known prior to our work. Along the way we also obtain new conditional lower bounds for the Single-Source-Max-Flow problem.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages41-50
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Externally publishedYes
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
Country/TerritoryUnited States
CityPortland
Period6/14/156/17/15

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Matching triangles and basing hardness on an extremely popular conjecture'. Together they form a unique fingerprint.

Cite this