首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Towards Better Separation between Deterministic and Randomized Query Complexity
  • 本地全文:下载
  • 作者:Sagnik Mukhopadhyay ; Swagato Sanyal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that there exists a Boolean function F which observes the following separations among deterministic query complexity ( D ( F )) , randomized zero error query complexity ( R 0 ( F )) and randomized one-sided error query complexity ( R 1 ( F )) : R 1 ( F ) = O ( D ( F ) ) and R 0 ( F ) = O ( D ( F ) ) 3 4 . This refutes the conjecture made by Saks and Wigderson that for any Boolean function f , R 0 ( f ) = ( D ( f ) ) 0 753 . This also shows widest separation between R 1 ( f ) and D ( f ) for any Boolean function. The function F was defined by G{\"{o}}{\"{o}}s, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D ( f ) and R 0 ( f ) , and polynomial separation between R 0 ( f ) and R 1 ( f ) . Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considerd in the work of Ambainis et al are different variants of F , we work with the original function F itself.

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