research
∙
06/21/2023
Optimal (degree+1)-Coloring in Congested Clique
We consider the distributed complexity of the (degree+1)-list coloring p...
share
research
∙
04/12/2023
On Parallel k-Center Clustering
We consider the classic k-center problem in a parallel setting, on the l...
research
∙
02/08/2023
Fast Parallel Degree+1 List Coloring
Graph coloring problems are arguably among the most fundamental graph pr...
research
∙
07/25/2022
Testing of Index-Invariant Properties in the Huge Object Model
The study of distribution testing has become ubiquitous in the area of p...
research
∙
04/26/2022
Tolerant Bipartiteness Testing in Dense Graphs
Bipartite testing has been a central problem in the area of property tes...
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 ...
research
∙
10/19/2021
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
The framework of distribution testing is currently ubiquitous in the fie...
research
∙
10/09/2021
A Faster Algorithm for Max Cut in Dense Graphs
We design an algorithm for approximating the size of Max Cut in dense gr...
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
∙
06/24/2020
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
The disjointness problem - where Alice and Bob are given two subsets of ...
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
∙
01/10/2018
FPT algorithms for embedding into low complexity graphic metrics
The Metric Embedding problem takes as input two metric spaces (X,D_X) an...
research
∙
08/05/2017