All reports by Author Arijit Ghosh:

__
TR20-135
| 9th September 2020
__

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

Revisions: 2

__
TR20-114
| 22nd July 2020
__

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar#### Disjointness through the Lens of Vapnikâ€“Chervonenkis Dimension: Sparsity and Beyond

__
TR20-108
| 19th July 2020
__

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar#### Query Complexity of Global Minimum Cut

Revisions: 1

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

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like \textsc{Degree}, \textsc{Neighbor}, and \textsc{Adjacency} queries.

Given $\epsilon \in (0,1)$, ... more >>>