PaperlayerView exact revision on arXiv

Source-linked AI summary

Separations in communication complexity using cheat sheets and information complexity

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

arXiv:1605.01142v2quant-phcs.CC

TL;DR

For total functions, the known quantum-versus-randomized communication separation was quadratic, while partial functions already admitted exponential separations. The paper ports cheat-sheet ideas through lookup functions and establishes separations of power 2.5, power 1.5, and nearly quadratic scale across its three comparisons.

  • Problem

    For total functions, the largest known separation between bounded-error quantum and randomized communication complexity was quadratic, despite exponential separations for partial functions.

    Source: §1 · p. 2

  • Method

    The paper develops communication lookup functions that generalize cheat-sheet constructions and prove randomized communication and information complexity lower bounds under mild conditions.

    Source: §1.2 · pp. 4–5

  • Results

    The paper gives total-function separations R(F) = eΩ(Q(F)^2.5), R(F) = eΩ(QE(F)^1.5), and R(F) ≥ UN(F)^(2−o(1)).

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Lookup functions provide a communication-complexity route to cheat-sheet-style separations, with lower bounds for both randomized communication and information complexity.

    Source: §1.2 · p. 4

    For the third separation, a lower bound for a lookup function alone is insufficient because the analogous randomized communication composition bound for And_n is false.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ~1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to G\"o\"os, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.

1 Introduction

Communication complexity offers a setting for studying computational resources with meaningful lower bounds and applications across complexity theory. This section presents three communication separations and introduces lookup functions as a way to extend cheat-sheet techniques to communication complexity.

1 Introduction

  • Communication complexity is a nontrivial model for proving lower bounds, with applications to circuits, data structures, streaming algorithms, property testing, and linear and semidefinite programs.Source: §1 · p. 2
  • R(F) = eΩ(Q(F)^2.5) for a total function, the first super-quadratic separation between bounded-error quantum and randomized communication complexity for total functions.The prior largest separation was quadratic, witnessed by disjointness.Source: §1 · p. 2
  • R(F) = eΩ(QE(F)^1.5) for a total function, improving the previous best separation of approximately 1.15.The previous separation was due to Ambainis [Amb13].Source: §1 · p. 2
  • R(F) ≥ UN(F)^(2−o(1)) for a total function, making the partition bound quadratically smaller than R(F) possible.The partition bound is at most UN(F).Source: §1 · p. 3

1.1 Comparison with prior work

  • Query-complexity separations do not automatically yield randomized communication separations because no general lifting theorem for randomized query lower bounds is known.The paper therefore works directly in communication complexity; the related randomized result of G¨o¨os, Jayram, Pitassi, and Watson also required new communication techniques.Source: §1.1 · pp. 3–4

1.2 Techniques

  • The authors could not establish the planned approximate-conical-junta-degree bound, partly because the measure behaves poorly as the error parameter changes.Source: §1.2 · p. 4
  • A (F, G)-lookup function extends cheat-sheet constructions to communication functions, and its randomized communication and information complexities remain at least those of F under mild conditions on G.The information-complexity argument tracks both information and communication complexity.Source: §1.2 · pp. 4–5

2 Preliminaries and notation

This section defines communication and information-complexity measures and gathers information-theoretic facts used later, including results on prediction, minimax principles, protocol transcripts, and biased input distributions.

2 Preliminaries and notation

  • Public-coin randomized and bounded-error quantum communication complexity allow error at most 1/3, while exact quantum complexity requires certainty; information complexity lower-bounds randomized communication.The measures are denoted R(F), Q(F), QE(F), and IC(F), respectively.Source: §2 · pp. 5–6
  • Nondeterministic complexity measures the largest certificate length, while unambiguous complexity requires exactly one certificate per valid input and equals log χ(F).Certificates are labels of monochromatic rectangles in a cover; χ(F) is the least number of monochromatic rectangles in a partition of the input space.Source: §2 · p. 6

2.1 Information theory

  • Markov’s inequality yields a useful conditional-to-joint bound: if the conditional expectation exceeds α on fewer than β probability mass, then f exceeds 100α jointly with probability less than β + 0.01.This corollary applies to nonnegative f over correlated X and Y.Source: §2.1 · p. 6

2.1.1 Distance measures

  • Total variation and Hellinger distances are interchangeable up to a quadratic factor; the paper uses Hellinger distance only for the Pythagorean property in the proof of Theorem 6.Total variation also satisfies triangle inequality, product-distribution bounds, monotonicity under taking marginals, and a partial-measurement identity.Source: §2.1.1 · pp. 7–8

2.1.2 Markov chains

  • A Markov chain X ↔ Y ↔ Z means X and Z are conditionally independent given Y, and its total-variation dependence is bounded by the sum of the pairwise dependences through Y.The section notes that Markov chains are used because of the independence fact introduced in Section 2.2.Source: §2.1.2 · pp. 8–9

2.1.3 Mutual information

  • Mutual information obeys chain rule, nonnegativity, monotonicity, bar hopping, independence, and data processing; in particular, a Markov chain cannot increase information from X to Z beyond I(X : Y).Conditional mutual information is the expectation over Z of I(X : Y | Z = z).Source: §2.1.3 · p. 9
  • Mutual information lower-bounds squared total variation: I(X : Y) ≥ ∆²(XY, X ⊗Y), and this bound is tight up to constants in the supplied binary-variable example.For the example, I(A : B) = δ and ∆(pB0, (1 − p)B1) = δ/2 when p = 1/2.Source: §2.1.3 · pp. 10–11
  • For binary A, Fact 12 turns mutual information I(A : B) into a measurement-based prediction advantage of at least I(A : B)/3.Source: §2.1.3 · p. 11

2.2 Communication complexity

  • For a partial function, the section defines worst-case randomized communication cost, distributional and worst-case information cost, and their bounded-error function measures, with ICε(F) ≤ Rε(F).The transcript includes messages and public coins; unless specified otherwise, ε = 1/3.Source: §2.2 · p. 12
  • Error can be reduced by repeating a protocol and taking a majority vote, increasing communication and information complexity by repetition factors.The passages describe first reducing error close to 1/2 to a constant, then using O(log(1/δ)) repetitions to reach error δ.Source: §2.2 · p. 12
  • Yao’s minimax principle equates worst-case randomized communication complexity with the hardest distributional complexity, while Braverman’s information minimax principle converts per-distribution protocols into a randomized protocol with scaled error and information bounds.For α ∈ (0, 1), the latter gives err(Π′) ≤ ε/α and IC(Π′) ≤ I/(1 − α).Source: §2.2 · p. 13
  • When inputs X and Y are independent, their transcript Π forms a Markov chain X ↔ Π ↔ Y, and protocol transcript distances satisfy the stated Pythagorean inequality [BJKS04].For inputs (x, y) and (x′, y′), h2(Π(x, y), Π(x′, y)) + h2(Π(x, y′), Π(x′, y′)) ≤ 2 · h2(Π(x, y), Π(x′, y′)).Source: §2.2 · p. 13
  • If a protocol transcript contains information about F’s output, Alice can predict the output and send one additional bit, increasing information cost by at most 1 and communication by exactly 1 bit.The resulting protocol predicts F with success probability greater than 1/2.Source: §2.2 · pp. 13–14
  • For i.i.d. pairs from µ, either F has a protocol with communication cost 1, information cost ≤1, and error ≤1/2−ε, or ∆(XL, X⊗W^⊗c)≤cε, where W is uniform on {0,1}.Source: §2.2 · p. 14

3 Lookup functions in communication complexity

This section introduces (F, G)-lookup functions as a communication-complexity analogue of cheat-sheet functions and establishes upper and lower bounds, including a lower bound relating their protocols to protocols for F with polynomial losses in communication and information complexity. The proof concludes by deriving a worst-case error above 1/3, contradicting the assumed error below 1/3.

3 Lookup functions in communication complexity

  • A (F, G)-lookup function uses F on c input pairs to select one of 2^c functions Gi; if any pair lies outside dom(F), its output instead comes from G0.The function is total even when F is partial, and the construction is inspired by query-complexity cheat-sheet functions [ABK16].Source: §3 · pp. 14–15

3.1 Upper bound

  • When G is consistent outside F, a quantum protocol can compute the c F values with repetition, then evaluate the selected Gi; the resulting complexity is O(Q(F) · c log c) + maxi O(Q(Gi)).Consistency ensures correctness when an input pair falls outside dom(F), even if the computed address differs from the prescribed fallback address.Source: §3.1 · pp. 15–16

3.2 Lower bound

  • The lower-bound argument aims to turn a bounded-error protocol for FG into one for F with only polynomial-in-c increases in communication and information complexity.Its intuition is that evaluating the selected Gi requires knowing the relevant cell uℓ, vℓ, which requires learning ℓ = F^c(x, y).Source: §3.2 · p. 16

3.2.1 Main result

  • For c ≥ log R(F) and a nontrivial XOR family G, any 1/3-error protocol for FG yields a 1/3-error protocol for F with IC(Π′) ≤ O(c^3 IC(Π)) and CC(Π′) ≤ O(c^2 CC(Π)).Consequently, R(FG) = Ω(R(F)/c^2) and IC(FG) = Ω(IC(F)/c^3).Source: §3.2.1 · pp. 16–17
  • For each input distribution on dom(F), the proof constructs a protocol for F, rules out simultaneous low-information conditions via a contradiction, and uses minimax to obtain a protocol correct on all inputs.The contradiction uses that the transcript changes little when conditioned on the selected cell, despite the need to evaluate that cell.Source: §3.2.1 · pp. 17, 19

3.2.2 Proofs of claims

  • Protocol Π has worst-case error at least 0.5−0.1 > 1/3, contradicting the assumption that its error is less than 1/3.Source: §3.2.2 · p. 23

4 Randomized lower bounds for Theorem 1 and Theorem 2

The section proves randomized communication lower bounds for the functions used in both separations, by lifting query-complexity constructions and applying conical-junta degree bounds. Its central lower bounds are R(Str ◦IPb) = eΩ(n^2.5) and R(Ptrn,m ◦IPb) = Ω(nm).

4 Randomized lower bounds for Theorem 1 and Theorem 2

  • The proof lifts Str and Ptr to two-party functions by composing them with the inner-product function IPb, then uses lookup functions to obtain the final separation constructions.For Theorem 1, the lookup family is consistent outside F and its members have quantum communication complexity eO(n), using distributed Grover search to verify inputs.Source: §4 · pp. 23–24
  • R(Str ◦IPb) = eΩ(n^2.5) and R(Ptrn,m ◦IPb) = Ω(nm), giving the randomized communication lower bounds needed for both separations.Theorem 7 establishes these bounds for m ≤ n and b ≥ t log n, for a sufficiently large constant t.Source: §4 · p. 24

4.1 Conical junta degree

  • The conical-junta composition theorem combines certificates for component functions, but requires regularity conditions that motivate constructing certificates of a special form.The composition theorem applies to partial functions when dual certificates are supported on the function’s domain.Source: §4.1 · pp. 25–26

4.1.1 Junta certificate for Simonn

  • For Simonn, a pair of distributions supported on its 1- and 0-inputs makes every small-width conjunction accept under the 1-distribution with comparable probability under the 0-distribution.This one-sided robustness property supplies a special-form junta certificate; the stated query-complexity bounds are Rdt(Simonn) = Ω(√n) and Qdt(Simonn) = O(log n log log n).Source: §4.1.1 · pp. 26–27

4.1.2 Junta certificates for Orn, Andn and Pr-Orn

  • Orn and Andn have two-sided (n/2, n) junta certificates, while the negation of Pr-Orn has a one-sided (n/2, 0) certificate.The Orn construction uses distributions uniform on inputs of Hamming weight 0, 1, and 2; duality gives the Andn certificate.Source: §4.1.2 · pp. 27–28

4.1.3 Junta degree lower bounds

  • Composing the component certificates yields deg+ε(Str) = Ω(n^2.5), and gives the corresponding junta-degree lower bound for Ptrn,m.For Str, the Orn ◦Andn certificate is composed with Simonn’s certificate; for Ptrn,m, certificates for ¬Pr-Orn and Andm are composed.Source: §4.1.3 · p. 29

4.2 From query to communication

  • The lifting theorem converts the approximate conical-junta degree lower bounds into randomized communication lower bounds for the corresponding functions composed with IPb.Theorem 7 follows from the lifting theorem and the degree bounds in Theorem 8.Source: §4.2 · p. 29

5 Quantum upper bounds

Lookup functions yield total communication problems with super-quadratic randomized-versus-quantum gaps and a 1.5-power randomized-versus-exact-quantum gap. Their upper bounds use quantum query composition and certificate checks that can be verified by distributed search.

5 Quantum upper bounds

  • Composition bounds convert query algorithms into communication upper bounds: Fact 30 bounds composed query complexity, and Fact 31 lifts query bounds to communication problems.The proof applies these facts to establish the upper bounds for F and the lookup-family functions.Source: §5 · p. 29, §5.1 · pp. 29–30

5.1 Proof of Theorem 1

  • R(FG) = eΩ(n^2.5) while Q(FG) = eO(n) for a total lookup function with b = Θ(log n).The construction takes F = Str ◦ IP_b and uses c = 10 log n.Source: §5.1 · p. 30
  • The 5.1 certificates encode a purported vector q and coordinate witnesses, so distributed Grover search can check the required n² conditions using eO(bn) quantum communication.Alice and Bob first exchange n bits to learn q; each condition can be evaluated with O(b + log n) communication.Source: §5.1 · pp. 30–31

5.2 Proof of Theorem 2

  • The 5.2 helper function checks certificates for at least n − 1 zero coordinates, and the resulting family is an XOR function consistent outside H.The proof uses these properties to apply the lookup lower-bound theorems.Source: §5.2 · p. 31
  • For m = Θ(√n), Theorem 12 gives a total lookup function HG with R(HG) = eΩ(mn) and an exact-quantum upper bound eO(√(nm) + n).The upper-bound expression is supported across the split passages p028, p029, and p041.Source: §5.2 · p. 31

6 Partitions vs. randomized communication

This section constructs total functions whose randomized communication complexity is nearly quadratic in UN. It iterates cheat-sheet functions and Tribes composition, using bounds on certificate and information complexity to establish the separation.

6 Partitions vs. randomized communication

  • Starting from disjointness, the construction alternates taking a cheat-sheet function and composing with Tr_n² = Or_n ◦ And_n, yielding a gap converging to quadratic.For each iteration, F_{i+1} := Tr_n² ◦ (F_i)_CS.Source: §6 · pp. 32, 34
  • Cheat-sheet and Tribes composition bounds control certificate complexity: N(F_CS) = O(N(F) log N), while UN(Tr_n² ◦ F_CS) = O(n UN(F) log N + n² N(F) log N).The construction uses these upper bounds to control UN across iterations.Source: §6 · p. 33
  • Composing with Or_n or And_n yields a protocol for F with the corresponding one-sided information complexity reduced by a factor n, while communication complexity remains O(CC(Π)).The displayed bounds are IC0(Π′) = O(IC0(Π)/n) for Or_n ◦ F and IC1(Π′) = O(IC1(Π)/n) for And_n ◦ F.Source: §6 · p. 34
  • There exists a total function F with R(F) ≥ UN(F)^(2-o(1)).The proof chooses an iteration count k that grows slowly with n.Source: §6 · pp. 32, 36
Loading 1605.01142v2…