首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:A Composition Theorem for Randomized Query complexity
  • 本地全文:下载
  • 作者:Anurag Anshu ; Dmitry Gavinsky ; Rahul Jain
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Let the randomized query complexity of a relation for error probability be denoted by \R ( ) . We prove that for any relation f 0 1 n and Boolean function g : 0 1 m 0 1 , \R 1 3 ( f g n ) = ( \R 4 9 ( f ) \R 1 2 − 1 n 4 ( g )) , where f g n is the relation obtained by composing f and g . We also show using an XOR lemma that \R 1 3 f g O ( log n ) n = ( log n \R 4 9 ( f ) \R 1 3 ( g )) , where g O ( log n ) is the function obtained by composing the XOR function on O ( log n ) bits and g .

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