A composition theorem for randomized query complexity

• المؤلفون الرئيسيون: Anshu, Anurag, Gavinsky, Dmitry, Jain, Rahul, Kundu, Srijita, Lee, Troy, Mukhopadhyay, Priyanka, Santha, Miklos, Sanyal, Swagato
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: 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...