An Adaptive Step Toward the Multiphase Conjecture

Young Kun Ko, Omri Weinstein

In 2010, Pǎtraşcu proposed the following three-phase dynamic problem, as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures: I: Prep…