A composition theorem for randomized query complexity

• Main Authors: Anshu, Anurag, Gavinsky, Dmitry, Jain, Rahul, Kundu, Srijita, Lee, Troy, Mukhopadhyay, Priyanka, Santha, Miklos, Sanyal, Swagato
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2018
• 主題: Decision Trees; DRNTU::Science::Mathematics; Query Algorithms And Complexity
• 在線閱讀: https://hdl.handle.net/10356/89383; http://hdl.handle.net/10220/46216
• 機構: Nanyang Technological University

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation ob...