Pointer-chasing is a central problem in two-party communication complexity: given input size n and a parameter k, the two players Alice and Bob are given functions \(N_A, N_B: [n] \rightarrow [n]\) , respectively, and their goal is to compute the value of \(p_k\) , where \(p_0 = 1\) , \(p_1 = N_A(p_0)\) , \(p_2 = N_B(p_1) = N_B(N_A(p_0))\) , \(p_3 = N_A(p_2) = N_A(N_B(N_A(p_0)))\) and so on, applying \(N_A\) in even steps and \(N_B\) in odd steps, for a total of k steps. In some versions of the problem, the final output is not \(p_k\) itself, but rather some fixed function \(f(p_k)\) of \(p_k\) . It is trivial to solve the problem using k communication rounds, with Alice speaking first, by simply “chasing the function” for k steps. Many works have studied the communication complexity of pointer chasing, although the focus has always been on protocols with \(k-1\) communication rounds, or with k rounds where Bob (the “wrong player”) speaks first. Many works have studied this setting giving sometimes tight or near-tight results. In this paper we study the communication complexity of the pointer chasing problem when the interaction between the two players is unlimited, i.e., without any restriction on the number of rounds. Perhaps surprisingly, this question was not studied before, to the best of our knowledge. Our main result is that the trivial k-round protocol is nearly tight (even) when the number of rounds is not restricted: we give a lower bound of \(\varOmega (k \log (n/k))\) on the randomized communication complexity of the pointer chasing problem with unlimited interaction, and a somewhat stronger lower bound of \(\varOmega (k \log \log {k})\) for protocols with zero error. When combined with prior work, our results also give a nearly-tight bound on the communication complexity of protocols using at most \(k-1\) rounds, across all regimes of k; for \(k > \sqrt{n}\) there was previously a significant gap between the upper and lower bound.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Pointer Chasing with Unlimited Interaction

  • Orr Fischer,
  • Rotem Oshman,
  • Adi Rosén,
  • Tal Roth

摘要

Pointer-chasing is a central problem in two-party communication complexity: given input size n and a parameter k, the two players Alice and Bob are given functions \(N_A, N_B: [n] \rightarrow [n]\) , respectively, and their goal is to compute the value of \(p_k\) , where \(p_0 = 1\) , \(p_1 = N_A(p_0)\) , \(p_2 = N_B(p_1) = N_B(N_A(p_0))\) , \(p_3 = N_A(p_2) = N_A(N_B(N_A(p_0)))\) and so on, applying \(N_A\) in even steps and \(N_B\) in odd steps, for a total of k steps. In some versions of the problem, the final output is not \(p_k\) itself, but rather some fixed function \(f(p_k)\) of \(p_k\) . It is trivial to solve the problem using k communication rounds, with Alice speaking first, by simply “chasing the function” for k steps. Many works have studied the communication complexity of pointer chasing, although the focus has always been on protocols with \(k-1\) communication rounds, or with k rounds where Bob (the “wrong player”) speaks first. Many works have studied this setting giving sometimes tight or near-tight results. In this paper we study the communication complexity of the pointer chasing problem when the interaction between the two players is unlimited, i.e., without any restriction on the number of rounds. Perhaps surprisingly, this question was not studied before, to the best of our knowledge. Our main result is that the trivial k-round protocol is nearly tight (even) when the number of rounds is not restricted: we give a lower bound of \(\varOmega (k \log (n/k))\) on the randomized communication complexity of the pointer chasing problem with unlimited interaction, and a somewhat stronger lower bound of \(\varOmega (k \log \log {k})\) for protocols with zero error. When combined with prior work, our results also give a nearly-tight bound on the communication complexity of protocols using at most \(k-1\) rounds, across all regimes of k; for \(k > \sqrt{n}\) there was previously a significant gap between the upper and lower bound.