Timeline for Communication complexity of graph isomorphism with 2-sided error
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 18 at 10:31 | history | edited | Dan | CC BY-SA 4.0 |
added 223 characters in body
|
| Oct 18 at 9:19 | comment | added | Dan | @JoshuaGrochow: I'm actually just curious about the communication complexity of this problem in general. Since the "natural" version is too easy, I thought the version I asked (both the one that got answered already, the multi-graph version, and the promise version) should have been studied, but I couldn't find anything in the literature. By the way, the promised version would be how I interpret the way Yao defined the problem in dl.acm.org/doi/pdf/10.1145/800076.802483. | |
| Oct 18 at 9:14 | vote | accept | Dan | ||
| Oct 17 at 15:28 | comment | added | Joshua Grochow | Interesting problem - curious where you came across it. To me, a more "natural" communication version of GI is that each player gets a graph, and they must communicate to decide whether the two graphs are isomorphic... Not arguing against your version, just curious how/where it arises. | |
| Oct 17 at 11:16 | answer | added | domotorp | timeline score: 2 | |
| Oct 17 at 8:26 | comment | added | Dan | I understand your point now. I have edited the problem to clarify this. | |
| Oct 17 at 8:26 | history | edited | Dan | CC BY-SA 4.0 |
Clarify if this is a promised problem
|
| Oct 16 at 11:22 | comment | added | domotorp | A "promise problem" in complexity theory means a problem where the inputs are promised to satisfy some property that the player(s) can(not) check. In your case, the players have no way of knowing that they are indeed given a partition of the graphs, because some edges might be repeated. So what happens if both of them hold the same edge of $G$? Can their output be arbitrary? Or do you rather define $G$ as the union of edges held by the players? | |
| Oct 16 at 8:17 | comment | added | Dan | Thanks for the question. It's not a promised problem. This is a standard set up for graph problems. A deterministic lower bound was claimed in Theorem 6 in dl.acm.org/doi/pdf/10.1145/800076.802483 (but with today's understanding, one can just derive this easily via fooling set). For n*polylog(n) protocol, I'm not sure it's published anywhere. The idea is to define the total order among isomorphic graphs. Let G' and H' be the graphs that are minimal in this order that are isomorphic to G and H. Then Alice and Bob just need hashing to check if G'=H'. | |
| Oct 15 at 19:03 | comment | added | domotorp | Is this a promise problem, or how do you ensure that they have a partition? Also, it would be nice to provide a link for the $n polylog(n)$ rnd protocol you mention. | |
| Oct 14 at 14:49 | history | asked | Dan | CC BY-SA 4.0 |