Popular conjectures imply strong lower bounds for dynamic problems

Amir Abboud, Virginia Vassilevska Williams

We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in t…