Title: Quantum Distributed Complexity of Graph Diameter and Set DisjointnessSpeaker: Ashwin Nayak Affiliation:
University of WaterlooZoom: Please email Emma Watson
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?