An Adaptive Step Toward the Multiphase Conjecture and Lower Bounds on Nonlinear Networks

Download paper here

In 2010, Psatrascu proposed the Multiphase problem as a candidate for proving polynomial lower bounds on the operational time of dynamic data structures, and showed it would imply unconditional lower bounds on many important dynamic data structure problems. After 10 years, there has been almost no progress on this conjecture. We show an ~\Omega(\sqrt{n}) cell-probe lower bound on the Multiphase problem for data structures with general (adaptive) updates, and queries with unbounded but “layered” adaptivity. This captures all known set-intersection data structures and significantly strengthens previous Multiphase lower bounds, which only captured non-adaptive data structures. Our main technical result is a communication lower bound on a 4-party variant of Patrascu’s Number-On-Forehead game, using information complexity techniques.