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
∙
11/09/2020
Hardness of Approximation of Euclidean k-Median
The Euclidean k-median problem is defined in the following manner: given...
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
∙
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
∙
12/02/2019
Noisy, Greedy and Not So Greedy k-means++
The k-means++ algorithm due to Arthur and Vassilvitskii has become the m...
research
∙
09/25/2019
Streaming PTAS for Binary ℓ_0-Low Rank Approximation
We give a 3-pass, polylog-space streaming PTAS for the constrained binar...
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
∙
08/02/2018
Triangle Estimation using Polylogarithmic Queries
Estimating the number of triangles in a graph is one of the most fundame...
research
∙
12/19/2017