Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

ISSN 1433-8092 | Imprint