Quadratically Tight Relations for Randomized Query Complexity

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^2/3 ≤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)^3/2). 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 \(\mathsf {D}^{\mu }_{\epsilon }(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.

1. Jain and Klauck in their paper defined prt_𝜖(f) to be the value of the linear program, instead of the logarithm of the value of the program.

This work is supported in part by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13, the Ministry of Education, Singapore under the Research Centres of Excellence programme by the Tier-3 grant Grant “Random numbers from quantum processes” No. MOE2012-T3-1-009.

M.S. is partially funded by the ANR Blanc program under contract ANR-12-BS02-005 (RDAM project).

J.V. is supported by the ERC Advanced Grant MQC. Part of this work was done while J.V. was an intern at the Centre for Quantum Technologies at the National University of Singapore.

We thank Anurag Anshu for helpful discussions.

Authors and Affiliations

1. Centre for Quantum Technologies, National University of Singapore, Block S15, 3 Science Drive 2, Singapore, Singapore, 117543

   Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha & Swagato Sanyal

2. MajuLab, UMI 3654, Singapore, Singapore

   Rahul Jain

3. SPMS, Nanyang Technological University, 21 Nanyang Link, Singapore, Singapore, 637371

   Hartmut Klauck, Troy Lee & Swagato Sanyal

4. IRIF, Université Paris Diderot, CNRS, 75205, Paris, France

   Miklos Santha

5. Centre for Quantum Computer Science, Faculty of Computing, University of Latvia, Raiņa 19, Riga, Latvia, LV-1586

   Jevgēnijs Vihrovs

Corresponding author

Correspondence to Jevgēnijs Vihrovs.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the Topical Collection on Computer Science Symposium in Russia (2018)

Appendix A: Analysis of Algorithm 1

For correctness, note that the algorithm outputs 1 on all 1-inputs. Thus assume x is a 0-input from here on in the analysis. Then we have to prove that \(\mathcal {A}\) outputs 0 with probability at least 1 − 𝜖. This amounts to showing that the function reduces to a constant 0 function and the algorithm terminates within ⌈EC(f)²/𝜖⌉ iterations with probability at least 1 − 𝜖. (For notational convenience, in what follows we will drop the ceilings and assume EC(f)²/𝜖 is an integer.)

Define a random variable T_k as

Let \(T = {\sum }_{k=1}^{\mathsf {EC}(f)^{2}/\epsilon } T_{k}\). As \({\sum }_{i \in [n]} w_{x}(i) \leq \mathsf {EC}(f)\) by definition, T > EC(f) implies that \(\mathcal {A}\) has terminated before point 2. Then it has returned 0, and the answer is correct. Let p = Pr[T > EC(f)]. We will prove that p ≥ 1 − 𝜖, in which case we would be done.

We continue by showing an upper and a lower bound on \(\mathbb {E}[T]\).

• The maximum possible value of T is at most

  $$ T \leq \sum\limits_{i \in [n]} w_{x}(i) + \frac{\mathsf{EC}(f)^{2}}{\epsilon} \cdot \frac{1}{\mathsf{EC}(f)} \leq \left( 1 + \frac{1}{\epsilon}\right) \mathsf{EC}(f). $$

  Therefore, \(\mathbb {E}[T] \leq p \cdot \left (1 + \frac {1}{\epsilon }\right ) \mathsf {EC}(f) + (1-p) \cdot \mathsf {EC}(f) = \left (1+\frac {p}{\epsilon }\right ) \mathsf {EC}(f)\).

• Let \(\mathcal {E}_{k}\) be the event that \(\mathcal {A}\) has terminated before the k-th iteration. In case \(\mathcal {A}\) performs the k-th iteration, let y be consistent 1-input chosen and the random variable i_k be the position that \(\mathcal {A}\) queries.

  $$ \begin{array}{@{}rcl@{}} \mathbb{E}[T_{k}] &=& \text{Pr}[\mathcal{E}_{k}] \cdot \frac{1}{\mathsf{EC}(f)} + \text{Pr}[\overline{\mathcal{E}_{k}}] \cdot \mathbb{E}[w_{x}(i_{k}) \mid \overline{\mathcal{E}_{k}}] \\ &\geq& \text{Pr}[\mathcal{E}_{k}] \cdot \frac{1}{\mathsf{EC}(f)} + \text{Pr}[\overline{\mathcal{E}_{k}}] \cdot \sum\limits_{i : x_{i} \neq y_{i}} w_{x}(i) \mu_{y}(i) \\ &=& \text{Pr}[\mathcal{E}_{k}] \cdot \frac{1}{\mathsf{EC}(f)} + \text{Pr}[\overline{\mathcal{E}_{k}}] \cdot \sum\limits_{i : x_{i} \neq y_{i}} w_{x}(i) w_{y}(i) / \sum\limits_{i \in [n]} w_{y}(i)\\ &\geq& \text{Pr}[\mathcal{E}_{k}] \cdot \frac{1}{\mathsf{EC}(f)} + \text{Pr}[\overline{\mathcal{E}_{k}}] \cdot \frac{1}{\mathsf{EC}(f)} \\ &=& \frac{1}{\mathsf{EC}(f)}, \end{array} $$

  The first inequality here follows from the fact that any i such that x_i≠y_i has not been queried yet, because x and y are both consistent with the queries made so far. Thus, the inequality holds regardless of the randomness chosen by \(\mathcal {A}\). The second inequality follows from the expectational certificate properties \({\sum }_{i:x_{i}\neq y_{i}} w_{x}(i)w_{y}(i) \geq 1\) and \({\sum }_{i \in [n]} w_{y}(i) \leq \mathsf {EC}(f)\). By the linearity of expectation, we have that \( \mathbb {E}[T] = {\sum }_{k = 1}^{\mathsf {EC}(f)^{2}/\epsilon } \mathbb {E}[T_{k}] \geq \mathsf {EC}(f)/\epsilon . \)

Combining the two bounds together, we get \(\frac {\mathsf {EC}(f)}{\epsilon } \leq \left (1+\frac {p}{\epsilon }\right ) \mathsf {EC}(f)\). Thus, p ≥ 1 − 𝜖.

Appendix B: Analysis of Algorithm 2

Proof of Theorem 2

We analize the correctness and performance of the algorithm for inputs sampled according to μ.

For each i = 2,…, 4bs(f), define T⁽ⁱ⁾ to be the event that \(\mathcal {B}\) completes at least i − 1 iterations and define T⁽¹⁾ to be the true event. Let i be arbitrary, and assume that T⁽ⁱ⁾ occurs. Then A⁽ⁱ⁾ denotes the 𝜖-error certificate (under η⁽ⁱ⁾) picked in the i-th iteration in step 2a. Let b⁽ⁱ⁾ ∈{0, 1} be the value approximately certified by A⁽ⁱ⁾ under η⁽ⁱ⁾. Let \(E^{(i)} \subseteq A^{(i)}\) denote the set of inputs y ∈ A⁽ⁱ⁾ such that f(y)≠b⁽ⁱ⁾. Recall from Section 2\(Q_{A^{(i)}}\) is the set of variables set by A⁽ⁱ⁾. For each assignment \(s \in \{0,1\}^{Q_{A^{(i)}}}\) to the variables fixed by A⁽ⁱ⁾ and subset \(U \subseteq A^{(i)}\), let U ⊕ s denote the shift of U by the vector s. Formally (‘⊕’ stands for bitwise exlusive or),

For i ≥ 2, define \(\mathcal L^{(i)}\) to be the set of variables queried in first i − 1 iterations and define \(\mathcal L^{(1)}:=\varnothing \). Note that \(\eta ^{(i)}=\mu \mid _{x_{\mathcal L^{(i)}}}\), and η⁽ⁱ⁾ is a product distribution.

Define all the above random variables to be ⊥ if T⁽ⁱ⁾ does not take place. Now define

First we bound the number of queries made by \(\mathcal {B}\). Since \(\mathcal {B}\) terminates when either t₀ = 2bs(f) or t₁ = 2bs(f), it performs at most 4bs(f) − 1 many iterations. On the other hand since η⁽ⁱ⁾ is a product distribution for each i, therefore \(|A^{(i)}| \leq \mathsf {corr}^{\times }_{\min , \epsilon }(f)\). Therefore, the algorithm makes \(O(\mathsf {corr}^{\times }_{\min , \epsilon }(f) \cdot \mathsf {bs}(f))\) many queries.

Now we prove that it errs on at most 4𝜖 fraction of the inputs according to μ.

Proposition 2

For every i and\(s \in \{0,1\}^{Q_{A^{(i)}}}, \text {Pr}[x \!\in \! E^{(i)}\oplus s \mid T^{(i)}, x \!\in \! A^{(i)}\oplus s] \!\leq \! \epsilon \).

Proof

Condition on the events \(T^{(i)}, x \in A^{(i)}\oplus s\). Furthermore, condition on \(x_{\mathcal L^{(i)}}\). Notice that under this conditioning, the distribution of the input x is \(\eta ^{(i)}=\mu \mid _{x_{\mathcal L^{(i)}}}\).

If T⁽ⁱ⁾ occurs, A⁽ⁱ⁾ is an 𝜖-error b⁽ⁱ⁾-certificate under η⁽ⁱ⁾. So \(\text {Pr}_{x \sim \eta ^{(i)}}[x \in E^{(i)} \mid T^{(i)}, x \in A^{(i)}] \leq \epsilon \). Since η⁽ⁱ⁾ is a product distribution as observed before, we have that for each \(s \in \{0,1\}^{Q_{A^{(i)}}}, \text {Pr}_{x \sim \eta ^{(i)}}[x \in E^{(i)}\oplus s \mid T^{(i)}, x \in A^{(i)}\oplus s]=\text {Pr}_{x \sim \eta ^{(i)}}[x \in E^{(i)} \mid T^{(i)}, x \in A^{(i)}]\leq \epsilon \). The proposition follows. □

In particular, Proposition 2 implies that for all i = 1,…, 4bs(f),

Since \(\mathcal {B}\) runs for at most 4bs(f) − 1 < 4bs(f) steps, by (1), linearity of expectation and Markov’s inequality we have that

For i such that T⁽ⁱ⁾ occurs, define \(S^{(i)}:=\{j \in Q_{A^{(i)}} \mid x_{j} \neq A^{(i)}(j)\}\). The following proposition will play a central role in our analysis.

Proposition 3

Let \(i_{1} < i_{2}\). For each \(i \in \{i_{1}, i_{2}\}\), let T⁽ⁱ⁾happen andX⁽ⁱ⁾ = 0. Then \(f(x^{S^{(i)}})=b^{(i)}, S^{(i_{1})} \cap S^{(i_{2})}=\varnothing \). In particular, if \(b^{(i_{1})}=b^{(i_{2})}\) and \(f(x)=1-b^{(i_{1})}\) then \(S^{(i_{1})}\) and \(S^{(i_{2})}\) are disjoint sensitive blocks for x.

Proof

Clearly, \(x^{S^{(i)}} \in A^{(i)}\). Also, since \(X^{(i)}=0, x \notin E^{(i)}+s\) for any s. Thus \(x^{S^{(i)}} \notin E^{(i)}\). Hence \(f(x^{S^{(i)}})=b^{(i)}\). To see that \(S^{(i_{1})} \cap S^{(i_{2})}=\varnothing \), let \(j \in S^{(i_{1})}\). It is easy to see that \(i_{2}>i_{1}\) implies that the distribution \(\eta ^{(i_{2})}\) at step i₂ is supported only on inputs consistent with \(x_{Q_{A^{(i_{1})}}}\). Hence, if \(j \in Q_{A^{(i_{2})}}\), then \(x_{j}=A^{(i_{2})}(j)\) which implies that \(j \notin S^{(i_{2})}\). □

For the rest of the proof, condition on the event that \(\mathcal {B}\) terminates at iteration i. We will bound the probability that \(\mathcal {B}\) errs.

First, condition on the event that \(\mathcal {B}\) terminates in step 2d. Then the probability that it errs is \(\text {Pr}[x \in E^{(i)} \mid T^{(i)}, x \in A^{(i)}] \leq \epsilon \) (by Proposition 2 invoked with \(s=0^{Q_{A^{(i)}}}\)).

Next, condition on the event that \(\mathcal {B}\) terminates at step 2e, and t₀ = 2bs(f) (the case t₁ = 2bs(f) is symmetrical). By (2), |{i∣X⁽ⁱ⁾ = 1}|≥bs(f) with probability at most 4𝜖. Condition on |{i∣X⁽ⁱ⁾ = 1}| < bs(f). Then \(\mathcal {B}\) outputs 0. We claim that f(x) = 0 with probability 1. Towards a contradiction, assume that f(x) = 1. As t₀ = 2bs(f) and |{i∣X⁽ⁱ⁾ = 1}| < bs(f), then in at least 2bs(f) − (bs(f) − 1) = bs(f) + 1 iterations j ≤ i, b^(j) = 0 and X^(j) = 0. By Proposition 3, the blocks S^(j) for those j iterations are sensitive for x and are disjoint. Since any input can have at most bs(f) sensitive blocks, we have the desired contradiction.

Thus the probability that \(\mathcal {B}\) errs is at most \(\max \nolimits \{\epsilon , 4\epsilon \}=4\epsilon \). □

Appendix C: Proof of Lemma 5

Proof

Let c = prt_𝜖(f). Abusing notation, let \(\{w_{z,A}\}_{z,A}\) be a primal feasible point which minimizes the objective. Thus \({\sum }_{z,A}w_{z,A}\cdot 2^{|A|}=2^{c}\). We immediately have that,

implying,

Let μ be any product probability distribution on {0, 1}ⁿ (in fact, the proof works for any distribution μ). Without loss of generality, assume that, \(\text {Pr}_{x \sim \mu }[f(x)=1] \geq \text {Pr}_{x \sim \mu }[f(x)=0]\). We shall show that \(\mathsf {corr}_{2\epsilon }^{1,\mu }(f) \leq c + \log (1/\epsilon )\). That will prove the theorem.

If \(\text {Pr}_{x \sim \mu }[f(x)=0]=0\) then {0, 1}ⁿ is a 0-error 1-certificate of co-dimension 0, and we are done. From now on, we will assume that \(\text {Pr}_{x \sim \mu }[f(x)=0]>0\).

Equation 3 and The two primal constraints imply that for each x ∈{0, 1}ⁿ,

Multiplying (4) and (5) by μ_x, adding the former over f^− 1(1) and the later over f^− 1(0), and re-arranging the order of summations we have,

Dividing (6) by (7) (note that \({\sum }_{x \in f^{-1}(0)}\mu _{x} \neq 0\) by our assumption about μ), we have that,

The last inequality above holds because of our assumption about μ. This implies that there exists a subcube A with co-dimension \(|A| \leq c + \log (1/\epsilon )\) such that,

Thus,

In other words, A is a 2𝜖-error 1-certificate under μ. We have,

□

Note that in (5), a better upper bound of simply 𝜖 follows from the first primal constraint of the partition bound LP. This results in a slightly better error \(\frac {\epsilon }{1-\epsilon } < 2\epsilon \) for 𝜖 < 1/2. Thanks to the anonymous reviewer for pointing this out.

Appendix D: Proof of Lemma 6

Proof

Let x be such that fbs(f, x) = fbs(f), and let b = f(x). We construct a distribution μ such that \(\mathsf {corr}_{\epsilon }^{b,\mu }(f) \geq \mathsf {fbs}(f)\).

Suppose that x has k sensitive blocks \(B_{1}, \ldots , B_{k}\). Let \(u_{1}, \ldots , u_{k}\) be the corresponding solution to the fbs(f, x) linear program. Let c ∈ (0, 1 − 𝜖) be a constant and define μ(x) = c and \(\mu (x^{B_{i}}) = (1-c)\frac {u_{i}}{{\sum }_{i=1}^{k} u_{i}} = (1-c)\frac {u_{i}}{\mathsf {fbs}(f)}\). Clearly, μ is a probability distribution on {0, 1}ⁿ.

Let A be the shortest 𝜖-error b-certificate according to μ and recall that Q_A is the set of variables fixed by A. Any input \(x^{B_{i}}\) is inconsistent with A iff \(B_{i} \cap Q_{A} \neq \varnothing \), thus

We also have

by definition of A. Since \(\text {Pr}_{y \sim \mu }\left [ f(y) = b, y \in A\right ] = c\), this implies

Then we get

On the other hand, since \({\sum }_{i : j \in B_{i}} u_{i} \leq 1\) for each j ∈ [n], we have

Therefore,

Since the above relation is true for every c, we have,

Thus we have corr_𝜖(f) ≥fbs(f). □

Reprints and permissions