6 citations · 15 across the 9 of their papers we have counts for
17 papers
Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling
Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan
We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling. We show that the sample complexity for sum estimation is closely related to t…
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…
Hardness of Approximation of Euclidean -Median
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal
The Euclidean -median problem is defined in the following manner: given a set of points in , and an integer , find a set $C \subset \mathbb{…
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…
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 and they have to check if their sets intersect - is a central problem in the world of comm…
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…
Hyperedge Estimation using Polylogarithmic Subset Queries
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh +1
In this work, we estimate the number of hyperedges in a hypergraph , where denotes the set of vertices and ${\cal F}({\cal…
On Triangle Estimation using Tripartite Independent Set Queries
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh +1
Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the n…
Approximate Correlation Clustering Using Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal
Ashtiani et al. (NIPS 2016) introduced a semi-supervised framework for clustering (SSAC) where a learner is allowed to make same-cluster queries. More specifically, in their model,…
On the k-Means/Median Cost Function
Anup Bhattacharya, Yoav Freund, Ragesh Jaiswal
In this work, we study the -means cost function. Given a dataset and an integer , the goal of the Euclidean -means problem is to find a set of $…
Approximate Clustering with Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal +1
Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind…
Faster Algorithms for the Constrained k-means Problem
Anup Bhattacharya, Ragesh Jaiswal, Amit Kumar
The classical center based clustering problems such as -means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster ar…
Sampling in Space Restricted Settings
Anup Bhattacharya, Davis Issac, Ragesh Jaiswal +1
Space efficient algorithms play a central role in dealing with large amount of data. In such settings, one would like to analyse the large data using small amount of "working space…
A tight lower bound instance for k-means++ in constant dimension
Anup Bhattacharya, Ragesh Jaiswal, Nir Ailon
The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial centers when using the k-means heuristic. The algorithm is a simple s…