首页    期刊浏览 2025年02月17日 星期一
登录注册

文章基本信息

  • 标题:One-way Communication and Non-adaptive Decision Tree
  • 本地全文:下载
  • 作者:Swagato Sanyal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Let f be a Boolean function on n -bits, and \mathsf I P the inner-product function on 2 b bits. Let f \mathsf I P : = f \mathsf I P n be the two party function obtained by composing f with \mathsf I P . In this work we bound the one-way communication complexity of f \IP in terms of the non-adaptive query complexity of f , from below. Similar results are known for general communication protocols and adaptive decision trees, when the arity of the inner function (inner-product in our case) is at least logarithmic in n . We prove analogous results for one-way communication as long as b is a large enough constant. Let \sR \cc ( ) and \sD \cc ( ) denote the randomized -error and deterministic one-way communication complexity respectively. Let \sD \dt ( ) denote the deterministic non-adaptive query complexity. Let \rH \bin ( ) denote the binary entropy function. We prove that \begin{itemize} \item If f is a \emph{total} Boolean function and b 2 , then \sR \cc ( f \mathsf I P ) ( 1 − \rH \bin ( )) n ( b − 1 ) . \item If f is a partial Boolean function and b 4 , then \sD \cc ( f \mathsf I P ) = ( b \sD \dt ( f )) . \end{itemize}

国家哲学社会科学文献中心版权所有