slideshow 3

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.