Explore the fascinating world of quantum and classical communication complexity in this 25-minute conference talk. Delve into the differences between interactive two-way communication and simultaneous message passing (SMP) while examining bits, qubits, and their associated complexities. Investigate relations and functions, both partial and total, as you uncover the intricacies of communication complexity as a mathematical model of computation. Learn about the Gap Hamming problem, from its function to its relation, and understand why the Gap Hamming Relation (GHR) is considered challenging for R. Gain valuable insights into this cutting-edge field of computer science and quantum information theory.
Bare Quantum Simultaneity Versus Classical Interactivity in Communication Complexity
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
Interactive (two-way) communication
Simultaneous message passing (SMP)
Bits, qubits and complexities
Relations and functions - partial and total
Communication complexity is one of the most interesting among the mathematical models of computation...
The Gap Hamming: from the function to a relation
The Gap Hamming Relation (GHR)
Defining the GHR (continued)
GHR is hard for R (proof idea)
Conclusions
Taught by
Association for Computing Machinery (ACM)
