3 citations · 8 across the 15 of their papers we have counts for
4 papers · 1 filter
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +2
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently…
A Faster Algorithm for Max Cut in Dense Graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1
We design an algorithm for approximating the size of \emph{Max Cut} in dense graphs. Given a proximity parameter , our algorithm approximates the size of \em…
On the Complexity of Triangle Counting using Emptiness Queries
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
Beame et al. [ITCS 2018 & TALG 2021] introduced and used the Bipartite Independent Set (BIS) and Independent Set (IS) oracle access to an unknown, simple, unweighted and undirected…
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
Using geometric techniques like projection and dimensionality reduction, we show that there exists a randomized sub-linear time algorithm that can estimate the Hamming distance bet…