TY - GEN
T1 - An adaptive step toward the multiphase conjecture
AU - Ko, Young Kun
AU - Weinstein, Omri
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - 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{epsilon} 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 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ǎ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 times n linear operator x mapsto Ax using gates of degree k (width-k DNFs) must have Omega(m cdot n{1/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 (n{1+ Omega(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.
AB - 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{epsilon} 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 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ǎ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 times n linear operator x mapsto Ax using gates of degree k (width-k DNFs) must have Omega(m cdot n{1/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 (n{1+ Omega(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.
UR - http://www.scopus.com/inward/record.url?scp=85100337977&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100337977&partnerID=8YFLogxK
U2 - 10.1109/FOCS46700.2020.00075
DO - 10.1109/FOCS46700.2020.00075
M3 - Conference contribution
AN - SCOPUS:85100337977
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 752
EP - 761
BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PB - IEEE Computer Society
T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Y2 - 16 November 2020 through 19 November 2020
ER -