All reports by Author Sayantan Sen:

__
TR20-135
| 9th September 2020
__

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen#### Estimation of Graph Isomorphism Distance in the Query World

Revisions: 2

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>>