Anup Bhattacharya

activity

20142026

most citedApproximate Clustering with Same-Cluster Queries

6 citations · 15 across the 9 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.CC2020★ 1 cited

Hardness of Approximation of Euclidean $k$ -Median

Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal

The Euclidean $k$ -median problem is defined in the following manner: given a set $X$ of $n$ points in $R^{d}$ , and an integer $k$ , find a set $C \subset \mathbb{…

cs.DS2020

Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!

Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra +1

We study a graph coloring problem that is otherwise easy but becomes quite non-trivial in the one-pass streaming model. In contrast to previous graph coloring problems in streaming…

cs.CC2020

Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh +2

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

Hardness of Approximation of Euclidean k-Median

Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!

Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond

Hardness of Approximation of Euclidean $k$ -Median