Equality, Revisited
summary
Gives a simpler proof via killing correlations that reproduces the Θ(√n) private-coin SMP lower bound for Equality by showing encoded messages become near-product under conditioning, so referee cannot distinguish yes/no distributions. Classifies all Merlin (untrusted proof) variants, proving that a classical proof gives no short certificate for Equality (proof must be length ~n unless a·b≈n) while a quantum prover makes Equality and Inequality equally hard. Builds an untrusted quantum state transfer primitive and a near‑optimal protocol where Alice sends O(a log a) classical bits and Merlin O((n/a) log n) qubits, matching trade-offs up to log factors.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:42Communication Model
- 2:04Equality
- 3:09Previous results
- 6:15Protocols
- 10:33Approval
- 11:17Proof
- 18:54Nondeterministic
- 19:42Example
- 27:13Conclusion
related talks
16mAsynchronous Multi-Party Quantum Computation
10mQuery, Communication and Discrepancy
18mEqual Opportunity: A Correctness Condition for Ordered Consensus
01h 04mThe Easy Witness Lemma
27mOn Distributed Differential Privacy and Counting Distinct Elements
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
15mNecessary Conditions in Multi-Server Differential Privacy