slideshow 3

Complexity seminar

Bare quantum simultaneity versus classical interactivity in communication complexity

Dmitry Gavinsky


Friday, 2. October 2020 - 14:30 to 16:30

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.