3 citations · 8 across the 15 of their papers we have counts for
27 papers
From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries
Debarshi Chanda, Buddha Dev Das, Arijit Ghosh +1
We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of In…
Optimal non-adaptive algorithm for edge estimation
Arijit Bishnu, Debarshi Chanda, Buddha Dev Das +2
We present a simple nonadaptive randomized algorithm that estimates the number of edges in a simple, unweighted, undirected graph, possibly containing isolated vertices, using only…
On Estimating Degree Distribution in Streaming and Query Models
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
Given a graph with vertices and edges, let denote its complementary cumulative degree histogram (CCDH), and let be the -index…
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +3
The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on , where is so large that even reading…
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
Triangle counting and sampling are two fundamental problems for streaming algorithms. Arguably, designing sampling algorithms is more challenging than their counting variants. It m…
Optimal (degree+1)-Coloring in Congested Clique
Sam Coy, Artur Czumaj, Peter Davies +1
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node of degree is assigned a palette of colors, and the goal is to…
On Parallel -Center Clustering
Sam Coy, Artur Czumaj, Gopinath Mishra
We consider the classic -center problem {in the constant dimensional Euclidean space} under a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model…
Parallel Derandomization for Coloring
Sam Coy, Artur Czumaj, Peter Davies +1
Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designin…
Testing of Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +2
The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Compute…
Tolerant Bipartiteness Testing in Dense Graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1
Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser and Ron [FOCS'96 and JACM'98]. Though…
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…
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…
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…
Query Complexity of Global Minimum Cut
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
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, wh…
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…
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…
Efficiently Sampling and Estimating from Substructures using Linear Algebraic Queries
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
Given an unknown matrix having non-negative entries, the \emph{inner product} (IP) oracle takes as inputs a specified row (or a column) of and a vector $v \in…
Structural Parameterization for Graph Deletion Problems over Data Streams
Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay +2
The study of parameterized streaming complexity on graph problems was initiated by Fafianie et al. (MFCS'14) and Chitnis et al. (SODA'15 and SODA'16). Simply put, the main goal is…
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…
Almost optimal query algorithm for hitting set using a subset query
Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay +2
Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity.…
On the streaming complexity of fundamental geometric problems
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
In this paper, we focus on lower bounds and algorithms for some basic geometric problems in the one-pass (insertion only) streaming model. The problems considered are grouped into…