Name
Abstract | ||
|---|---|---|
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 -u003e {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 obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.FSTTCS.2017.10 | foundations of software technology and theoretical computer science |
DocType | Volume | Citations |
Journal | abs/1706.00335 | 0 |
PageRank | References | Authors |
0.34 | 6 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anurag Anshu | 1 | 43 | 14.24 |
| Dmitry Gavinsky | 2 | 166 | 20.21 |
| Rahul Jain | 3 | 784 | 71.51 |
| Srijita Kundu | 4 | 0 | 0.34 |
| Troy Lee | 5 | 276 | 28.96 |
| Priyanka Mukhopadhyay | 6 | 6 | 2.19 |
| Miklós Sántha | 7 | 96 | 7.95 |
| Swagato Sanyal | 8 | 1 | 3.39 |