Communication Complexity of Private Simultaneous Messages Protocols - 2021 ITC Conference

Explore the communication complexity of private simultaneous messages (PSM) protocols in this 22-minute conference talk from the 2021 ITC Conference. Delve into the quantum counterpart, private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement. Learn about the inevitable increase in communication cost due to privacy conditions in the two-party PSQM model, and discover the proven lower bound for communication complexity in PSQM protocols with shared random strings. Investigate the factor two gap between communication complexity of PSQM protocols with shared entangled states versus shared random strings, and uncover an exponential gap for a two-party partial function. Gain insights into multi-party computation, communication costs, and various models for communication complexity through this comprehensive presentation by Akinori Kawachi and Harumichi Nishimura from the Paul G. Allen School.

Intro
Multi-Party Computation (MPC)
Communication Cost of MPC
Models for Communication Complexity
Some Results on PSM protocols
Communication Complexity in SMP Randomness vs Entanglement
Our Results (1)
Proof Strategy (Classical lower bounds)
Proof Strategy (Quantum lower bounds)
Concluding Remarks