Title: Quantum Distributed Complexity of Graph Diameter and Set Disjointness
| Speaker: | Ashwin Nayak |
| Affiliation: |
University of Waterloo |
| Zoom: | Please email Emma Watson |
Abstract:
In the Congest model, a network of p processors cooperate to solve some distributed task. Initially, each processor knows only its unique label, the labels of its neighbours, and a polynomial upper bound on p, the size of the network. The processors communicate with their neighbours in rounds. In each round, a processor may perform local (quantum) computation, and send a short message to each of its neighbours. How many rounds of communication are required for some processor to compute the diameter of the network?
With classical communication, roughly p rounds are necessary and sufficient. Le Gall and Magniez (2018) designed a quantum algorithm for Graph Diameter in the Congest model with roughly sqrt{p Delta} rounds, where Delta is the diameter of the graph. They also showed that this is almost optimal, if each processor has small (polylog-size) local memory. However, without any restriction on the memory size, the lower bound was significantly smaller --- roughly sqrt{p} + Delta.
We prove a roughly (p Delta^2)^{1/3} unconditional round lower bound for Graph Diameter. We derive this via a distributed variant of Set Disjointess, a fundamental problem in communication complexity. We also present an algorithm for Set Disjointess in a related model, which simultaneously hints at the possibility of a better algorithm in the Congest model, and presents a barrier to improving the lower bound.
Joint work with Frederic Magniez.