A composition theorem for randomized query complexity
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...
Saved in:
Main Authors: | , , , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2018
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/89383 http://hdl.handle.net/10220/46216 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |