Quadratically Tight Relations for Randomized Query Complexity
- Publisher:
- Springer Science and Business Media LLC
- Publication Type:
- Journal Article
- Citation:
- Theory of Computing Systems, 2020, 64, (1), pp. 101-119
- Issue Date:
- 2020-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 2020_Article_ (2).pdf | Published version | 784.41 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R (f): C(f) ≤R (f) ≤C(f) . In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R (f): EC(f) ≤R (f) = O(EC(f) ). For R(f), we prove that EC ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f) and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R (f). The measure is also related to the fractional certificate complexity FC(f) as follows: FC(f) ≤EC(f) = O(FC(f) ). This also connects to an open question by Aaronson whether FC(f) is a quadratically tight bound for R (f), as EC(f) is in fact a relaxation of FC(f). In the second part of the work, we investigate whether the corruption bound corr (f) quadratically approximates R(f). By Yao’s theorem, it is enough to prove that the square of the corruption bound upper bounds the distributed query complexity D𝜖μ(f) for all input distributions μ. Here, we show that this statement holds for input distributions in which the various bits of the input are distributed independently. This is a natural and interesting subclass of distributions, and is also in the spirit of the input distributions studied in communication complexity in which the inputs to the two communicating parties are statistically independent. Our result also improves upon a result of Harsha et al. (2016), who proved a similar weaker statement. We also note that a similar statement in the communication complexity is open. 0 0 0 0 0 0 𝜖 2 2 2/3 2 3/2
Please use this identifier to cite or link to this item: