5 citations · 5 across the 4 of their papers we have counts for
10 papers · 1 filter
Improved Algorithms for Clustering with Noisy Distance Oracles
Pinki Pradhan, Anup Bhattacharya, Ragesh Jaiswal
Bateni et al. has recently introduced the weak-strong distance oracle model to study clustering problems in settings with limited distance information. Given query access to the st…
Improved Sublinear-time Moment Estimation using Weighted Sampling
Anup Bhattacharya, Pinki Pradhan
In this work we study the {\it moment estimation} problem using weighted sampling. Given sample access to a set with weighted elements, and a parameter , we estimate t…
Faster Counting and Sampling Algorithms using Colorful Decision Oracle
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh +1
In this work, we consider -{\sc Hyperedge Estimation} and -{\sc Hyperedge Sample} problem in a hypergraph in the query…
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…
Noisy, Greedy and Not So Greedy k-means++
Anup Bhattacharya, Jan Eube, Heiko Röglin +1
The k-means++ algorithm due to Arthur and Vassilvitskii has become the most popular seeding method for Lloyd's algorithm. It samples the first center uniformly at random from the d…
Streaming PTAS for Binary -Low Rank Approximation
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal +1
We give a 3-pass, polylog-space streaming PTAS for the constrained binary -means problem and a 4-pass, polylog-space streaming PTAS for the binary -low rank approximatio…