
Dmitri Gavinsky
 (IM CAS)

Quantum versus classical simultaneity in communication complexity

Abstract:

We will see a bipartite partial function, which has no efficient solution in the model of randomised simultaneous
message passing (with shared randomness), but has an efficient protocol in the model of quantum simultaneous message
passing – even without shared randomness.
This can be interpreted as the strongest known ? as of today ? example of "superclassical" capabilities of the
weakest studied model of quantum communication.

Klim Efremenko
 (TelAviv University)

Testing Equality in Communication Graphs

Abstract:

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$bit
string. Each player is allowed to communicate with its neighbors according
to a (static) agreed communication protocol and the players must decide,
deterministically, if their inputs are all equal. What is the minimum
possible total number of bits transmitted in a protocol solving
this problem? We determine this minimum up to a lower order
additive term in many cases (but not for all graphs).
In particular, we show that it is $kn/2+o(n)$ for any
Hamiltonian $k$vertex graph, and that for any $2$edge connected
graph with $m$ edges containing no
two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$.
The proofs combine graph theoretic ideas with
tools from additive number theory.
Michal Koucky, Pavel Pudlak
organizers