• 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 "super-classical" capabilities of the weakest studied model of quantum communication.
    • 02.06.17   13:30
    • Klim Efremenko
    • (Tel-Aviv 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.
    • 19.05.17   13:30

    Michal Koucky, Pavel Pudlak