I have some doubts for the relationship between communication complexity model and query complexity model. In my understanding, query complexity model are same as decision tree complexity model. Let $F(x, y) = f(g(x_{1}, y_{1}), ..., g(x_{n}, y_{n}))$, then based on lifting theorems, if the dimension $d$ of binary strings is large enough, then deterministic communication complexity of $F$ is equal up to $d$ times the decision tree complexity of of $f$.

My question is, could we basically draw the claim that all the complexity result on computing certain $f$ we obtain on query complexity model is similar (with some constant factor) as in communication complexity model on computing certain $F$, at least when $d$ is large ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.