View source for Reduction from Triangle Collection* to dynamic 4/3-Diameter

FROM: [[Triangle Collection*]] TO: [[dynamic 4/3-Diameter]]

== Description == 



== Implications == 

assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no static ${4}/{3}-\epsilon$ approximation with additive error $O(m^\delta)$ with running time $O(m^{\frac{3}{2}({1}-\delta)-\epsilon'})$ or incremental/decremental algorithm with amortized time $O(m^{\frac{1}{2}-\frac{3\delta}{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$

== Year == 

2016

== Reference == 

Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to diameter. arXiv preprint arXiv:1602.06705.

https://arxiv.org/abs/1602.06705