20 citations · 31 across the 15 of their papers we have counts for
25 papers
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…
Curves, points, incidences and covering
Arijit Bishnu, Mathew Francis, Pritam Majumder
Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve covers a point if the cu…
Arboricity Matters in Triangle Counting with Random Edges
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
Given a simple, unweighted, undirected graph with and , and parameters , along with Degree, Neighbour, Pair and RandomEdge query acce…
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…
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…
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…
The linear arboricity conjecture for graphs of low degeneracy
Manu Basavaraju, Arijit Bishnu, Mathew Francis +1
A linear forest is an acyclic graph whose each connected component is a path; or in other words, it is an acyclic graph whose maximum degree is at most 2. A linear coloring of a gr…
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…
Grid Obstacle Representation of Graphs
Arijit Bishnu, Arijit Ghosh, Rogers Mathew +2
The grid obstacle representation, or alternately, -obstacle representation of a graph is an injective function and a set of point o…
Uniformity of point samples in metric spaces using gap ratio
Arijit Bishnu, Sameer Desai, Arijit Ghosh +2
Teramoto et al. defined a new measure called the gap ratio that measures the uniformity of a finite point set sampled from , a bounded subset of . We generali…
On Packing Almost Half of a Square with Anchored Rectangles: A Constructive Approach
Sandip Banerjee, Aritra Banik, Bhargab B. Bhattacharya +2
In this paper, we consider the following geometric puzzle whose origin was traced to Allan Freedman \cite{croft91,tutte69} in the 1960s by Dumitrescu and T{ó}th \cite{adriancasaba2…
An Existential Proof of the Conjecture on Packing Anchored Rectangles
Sandip Banerjee, Aritra Banik, Bhargab B. Bhattacharya +2
Let be a set of points, including the origin, in the unit square . We consider the problem of constructing axis-parallel and mutually disjoint rectangl…
Linear kernels for k-tuple and liar's domination in bounded genus graphs
Arijit Bishnu, Arijit Ghosh, Subhabrata Paul
A set is called a -tuple dominating set of a graph if for all , where denotes the closed neighbo…
An Algorithm for Computing Constrained Reflection Paths in Simple Polygon
Arijit Bishnu, Subir Kumar Ghosh, Partha Pratim Goswami +2
Let be a source point and be a destination point inside an -vertex simple polygon . Euclidean shortest paths and minimum-link paths between and inside hav…
Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network
Dinesh Dash, Arijit Bishnu, Arobinda Gupta +1
The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of…