Complexity seminar
Bare quantum simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky
IM, CAS
Friday, 2. October 2020 - 14:30 to 16:30
https://cesnet.zoom.us/j/98453959650?pwd=TEpEbjNqYThDQzFaSHhxNEhZcEFVUT09
The password is the last name in small case of the famed British mathematician, the founder of computability theory.
We shall see a relational problem that is easy for the weakest quantum model of communication – simultaneous message passing (without shared resources); at the same time, the problem is difficult for the strongest classical model – interactive (two-way) communication.