research
∙
11/09/2022
Sampling an Edge in Sublinear Time Exactly and Optimally
Sampling edges from a graph in sublinear time is a fundamental problem a...
share
research
∙
08/02/2022
Bias Reduction for Sum Estimation
In classical statistics and distribution testing, it is often assumed th...
research
∙
03/17/2022
Triangle and Four Cycle Counting with Predictions in Graph Streams
We propose data-driven one-pass streaming algorithms for estimating the ...
research
∙
11/19/2021
Embeddings and labeling schemes for A*
A* is a classic and popular method for graphs search and path finding. I...
research
∙
10/28/2021
Approximating the Arboricity in Sublinear Time
We consider the problem of approximating the arboricity of a graph G= (V...
research
∙
10/25/2021
Sampling Multiple Nodes in Large Networks: Beyond Random Walks
Sampling random nodes is a fundamental algorithmic primitive in the anal...
research
∙
09/08/2021
Adversarially Robust Streaming via Dense–Sparse Trade-offs
A streaming algorithm is adversarially robust if it is guaranteed to per...
research
∙
07/14/2021
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
We consider the problem of sampling and approximately counting an arbitr...
research
∙
06/15/2021
Learning-based Support Estimation in Sublinear Time
We consider the problem of estimating the number of distinct elements in...
research
∙
12/07/2020
Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques: Sampling Cliques is Harder Than Counting
In this work, we consider the problem of sampling a k-clique in a graph ...
research
∙
08/18/2020
Amortized Edge Sampling
We present a sublinear time algorithm that allows one to sample multiple...
research
∙
02/19/2020
Parallel Algorithms for Small Subgraph Counting
Subgraph counting is a fundamental problem in analyzing massive graphs, ...
research
∙
02/21/2019
The Arboricity Captures the Complexity of Sampling Edges
In this paper, we revisit the problem of sampling edges in an unknown gr...
research
∙
11/11/2018
Faster sublinear approximations of k-cliques for low arboricity graphs
Given query access to an undirected graph G, we consider the problem of ...
research
∙
10/24/2017
Provable and practical approximations for the degree distribution using sublinear graph samples
The degree distribution is one of the most fundamental properties used i...
research
∙
09/13/2017