  In 2010, P\v{a}tra\c{s}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: Preprocess a collection of sets $\vec{S} = S_1, \ldots , S_k \subseteq
[n]$, where $k=\operatorname{poly}(n)$.
  II: A set $T\subseteq [n]$ is revealed, and the data structure updates its
memory.
  III: An index $i \in [k]$ is revealed, and the data structure must determine
if $S_i\cap T=^? \emptyset$.
  P\v{a}tra\c{s}cu conjectured that any data structure for the Multiphase
problem must make $n^\epsilon$ cell-probes in either Phase II or III, 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 P\v{a}tra\c{s}cu's Number-On-Forehead Multiphase game, using information
complexity techniques. We also show that a lower bound on P\v{a}tra\c{s}cu'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.
