research
∙
01/13/2022
Faster Counting and Sampling Algorithms using Colorful Decision Oracle
In this work, we consider d-Hyperedge Estimation and d-Hyperedge Sample ...
share
research
∙
10/08/2021
Bipartite Independent Set Oracles and Beyond: Can it Even Count Triangles in Polylogarithmic Queries?
Beame et al. [ITCS 2018] introduced and used the Bipartite Independent S...
research
∙
07/06/2021
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
Using geometric techniques like projection and dimensionality reduction,...
research
∙
10/25/2020
Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!
We study a graph coloring problem that is otherwise easy but becomes qui...
research
∙
07/17/2020
Query Complexity of Global Minimum Cut
In this work, we resolve the query complexity of global minimum cut prob...
research
∙
07/12/2020
The linear arboricity conjecture for 3-degenerate graphs
A k-linear coloring of a graph G is an edge coloring of G with k colors ...
research
∙
08/12/2019
Hyperedge Estimation using Polylogarithmic Subset Queries
A hypergraph H is a set system (U( H), F(H)), where U( H) denotes the s...
research
∙
06/18/2019
Inner Product Oracle can Estimate and Sample
Edge estimation problem in unweighted graphs using local and sometimes g...
research
∙
06/13/2019
Structural Parameterization for Graph Deletion Problems over Data Streams
The study of parameterized streaming complexity on graph problems was in...
research
∙
06/13/2019
Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
In this work, we initiate a systematic study of parameterized streaming ...
research
∙
08/02/2018
Triangle Estimation using Polylogarithmic Queries
Estimating the number of triangles in a graph is one of the most fundame...
research
∙
07/17/2018
Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
In this paper, we study the query complexity of parameterized decision a...
research
∙
03/19/2018
On the streaming complexity of fundamental geometric problems
In this paper, we focus on lower bounds and algorithms for some basic ge...
research
∙
08/05/2017