Tutte Colloquium - Ashwin NayakExport this event to calendar

Friday, November 26, 2021 — 3:30 PM EST

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.

Event tags 

S M T W T F S
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
  1. 2021 (101)
    1. December (1)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)