Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

DOI10.1145/2746539.2746594zbMath1321.68291OpenAlexW1973046087MaRDI QIDQ2941487

Amir Abboud, Huacheng Yu, Virginia Vassilevska Williams

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746594

zbMATH Keywords

reductions3SUMdynamic data structuresconditional lower boundsAPSPsethCNF-SATsingle-source max-flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)

Related Items (16)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item ⋮ Unnamed Item

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Matching Triangles and Basing Hardness on an Extremely Popular Conjecture