Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR19-144 | 30th October 2019 02:13

#### An Adaptive Step Toward the Multiphase Conjecture

Revision #1
Authors: Young Ko, Omri Weinstein
Accepted on: 30th October 2019 02:13
Keywords:

Abstract:

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.

### Paper:

TR19-144 | 29th October 2019 23:51

#### An Adaptive Step Toward the Multiphase Conjecture

TR19-144
Authors: Young Ko, Omri Weinstein
Publication: 30th October 2019 00:20
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint