首页    期刊浏览 2024年09月12日 星期四
登录注册

文章基本信息

  • 标题:Raz-McKenzie simulation with the inner product gadget
  • 本地全文:下载
  • 作者:Xiaodi Wu ; Penghui Yao ; Henry Yuen
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions f composed with the Inner Product gadget g I P ( x y ) = i x i y i mod 2 of logarithmic size. In other words, given a function f : 0 1 n 0 1 with deterministic query complexity D ( f ) , we show that the deterministic communication complexity of the composed function f g n I P is ( D ( f ) log n ) , where f g n I P ( x y ) = f ( g I P ( x 1 y 1 ) g I P ( x n y n )) where x = ( x 1 x n ) , y = ( y 1 y n ) and each x i and y i are O ( log n ) bit strings. In [Raz, McKenzie FOCS 1997] and [Göös, et al. FOCS 2015], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function f .

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