In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving polynomia l lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make n cell-probes in either the update or query phase, and showed that this would imply similar unconditiona l lower bounds on many important dynamic data structure problems. Alas, there has been almost no progress on this conjecture in the past decade since its introduction.

We show an ( n ) cell-probe lower bound on the Multiphase problem for data structures with general (adaptive) updates, and queries with unbounded but "layered" adaptivity. This result 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 Multiphase game, using information complexity techniques. We also show that a lower bound on Patrascu's original NOF game would imply a polynomial ( n 1+ ) lower bound on the number of wires of any constant-depth circuit with arbitrar y gates computing a random O ( n ) n linea r operator x A x , a long-standing open problem in circuit complexity. This suggests that the NOF conjecture is much stronger than its data structure counterpart.