An Adaptive Step Toward the Multiphase Conjecture

In 2010, Pătraşcu 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. He conjectured that any data structure for the Multiphase problem must make nεcell-probes in either update or query phases, and showed that this would imply similar unconditional lower bounds on many important dynamic data structure problems. 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 Pătraşcu's Number-On-Forehead Multiphase game, using information complexity techniques. We then use this result to make progress on understanding the power of nonlinear gates in networks computing linear operators, a long-standing open problem in circuit complexity and network design: We show that any depth- d circuit that computes a random m×n linear operator x→ Ax using gates of degree k (width- k DNFs) must have Ω(m·n1/2(d+k)) wires. Finally, we show that a lower bound on Pătraşcu's original NOF game would imply a polynomial wire lower bound (n1+Ω(1/d)) for circuits with arbitrary gates computing a random linear operator. This suggests that the NOF conjecture is much stronger than its data structure counterpart.