Matching triangles and basing hardness on an extremely popular conjecture
DOI10.1145/2746539.2746594zbMATH Open1321.68291OpenAlexW1973046087MaRDI QIDQ2941487FDOQ2941487
Authors: 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
Recommendations
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Higher lower bounds from the 3SUM conjecture
- Towards polynomial lower bounds for dynamic problems
- Threesomes, degenerates, and love triangles
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)
Cites Work
- Shortest-path queries in static networks
- Approximate distance oracles
- 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
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Approximate distance oracles with constant query time
- Fast C-K-R partitions of sparse graphs
- Automata, Languages and Programming
- Ramsey partitions and proximity data structures
Cited In (20)
- Title not available (Why is that?)
- Subquadratic algorithms for algebraic 3SUM
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Fooling views: a new lower bound technique for distributed computations under congestion
- Tighter connections between Formula-SAT and shaving logs
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Nearly optimal separation between partially and fully retroactive data structures
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- Higher lower bounds from the 3SUM conjecture
- Title not available (Why is that?)
- Towards hardness of approximation for polynomial time problems
- Towards polynomial lower bounds for dynamic problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fine-Grained Complexity Theory (Tutorial)
- On sequential functions and fine-grained cryptography
- Conditional hardness for sensitivity problems
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
Uses Software
This page was built for publication: Matching triangles and basing hardness on an extremely popular conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941487)
