About one-way model ·Power: As efficient as the best two-way protocol. -Efficient protocols for specific functions s such as Equality,Hamming Distance,and in general,all symmetric XOR functions. 。Applications: Lower bound for space complexity of streaming algorithms. Lower bound?Can be quite hard, especially for quantum
About one-way model • Power: – Efficient protocols for specific functions such as Equality, Hamming Distance, and in general, all symmetric XOR functions. • Applications: – Lower bound for space complexity of streaming algorithms. • Lower bound? Can be quite hard, especially for quantum. As efficient as the best two-way protocol
Question Question:What's the largest gap between classical and quantum communication complexities? Partial functions,relations:exponential. Total functions,two-way: -Largest gap:Q(Disj)=e(Vn),R(Disj)=e(n) -Best bound:R(f)=exp(Q(f)). ·Conjecture:R(f=poly(Q(f⑤)：
Question • Question: What’s the largest gap between classical and quantum communication complexities? • Partial functions, relations: exponential. • Total functions, two-way: – Largest gap: Q(Disj) = Θ(√n), R(Disj) = Θ(n). – Best bound: R(f) = exp(Q(f)). • Conjecture: R(f) = poly(Q(f))
Question Question:What's the largest gap between classical and quantum communication complexities? Partial functions,relations:exponential. Total functions,one-way: Largest gap:R1(EQ)=2.Q1(EQ), -Best bound:R1(⑤=exp(Q1(⑤)： ·Conjecture:R1(f⑤=poly(Q'(f), -or even R1(⑤=O(Q1(⑤)：
Question • Question: What’s the largest gap between classical and quantum communication complexities? • Partial functions, relations: exponential. • Total functions, one-way: – Largest gap: R1 (EQ) = 2∙Q1 (EQ), – Best bound: R1 (f) = exp(Q1 (f)). • Conjecture: R1 (f) = poly(Q1 (f)), – or even R1 (f) = O(Q1 (f))