In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving $polynomial$ lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make $n^\epsilon$ cell-probes in either the update or query phase, and showed that this would imply similar $unconditional$ 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 $\tilde{\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 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+\epsilon}$) lower bound on the number of wires of any constant-depth circuit with $arbitrary$ gates computing a random $\tilde{O}(n)\times n$ $linear$ operator $x \mapsto Ax$, a long-standing open problem in circuit complexity. This suggests that the NOF conjecture is much stronger than its data structure counterpart.

In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving $polynomial$ lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make $n^\epsilon$ cell-probes in either the update or query phase, and showed that this would imply similar $unconditional$ 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 $\tilde{\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 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+\epsilon}$) lower bound on the number of wires of any constant-depth circuit with $arbitrary$ gates computing a random $\tilde{O}(n)\times n$ $linear$ operator $x \mapsto Ax$, a long-standing open problem in circuit complexity. This suggests that the NOF conjecture is much stronger than its data structure counterpart.