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
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2018
• Subjects: Decision Trees; DRNTU::Science::Mathematics; Query Algorithms And Complexity
• Online Access: https://hdl.handle.net/10356/89383; http://hdl.handle.net/10220/46216
• Institution: 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...