ECCC-Report TR19-144https://eccc.weizmann.ac.il/report/2019/144Comments and Revisions published for TR19-144en-usWed, 30 Oct 2019 02:13:14 +0200
Revision 1
| An Adaptive Step Toward the Multiphase Conjecture |
Omri Weinstein,
Young Ko
https://eccc.weizmann.ac.il/report/2019/144#revision1In 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.
Wed, 30 Oct 2019 02:13:14 +0200https://eccc.weizmann.ac.il/report/2019/144#revision1
Paper TR19-144
| An Adaptive Step Toward the Multiphase Conjecture |
Omri Weinstein,
Young Ko
https://eccc.weizmann.ac.il/report/2019/144In 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.
Wed, 30 Oct 2019 00:20:01 +0200https://eccc.weizmann.ac.il/report/2019/144