research
∙
07/02/2023
Massively Parallel Algorithms for the Stochastic Block Model
Learning the community structure of a large-scale graph is a fundamental...
share
research
∙
07/01/2023
Effective Resistances in Non-Expander Graphs
Effective resistances are ubiquitous in graph algorithms and network ana...
research
∙
05/22/2023
An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs
We revisit the relation between two fundamental property testing models ...
research
∙
04/07/2023
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing
We study property testing of properties that are definable in first-orde...
research
∙
10/23/2022
Sublinear-Time Algorithms for Max Cut, Max E2Lin(q), and Unique Label Cover on Expanders
We show sublinear-time algorithms for Max Cut and Max E2Lin(q) on expand...
research
∙
06/28/2022
Sublinear-Time Clustering Oracle for Signed Graphs
Social networks are often modeled using signed graphs, where vertices co...
research
∙
03/27/2022
Approximately Counting Subgraphs in Data Streams
Estimating the number of subgraphs in data streams is a fundamental prob...
research
∙
02/17/2022
Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle
The stochastic block model (SBM) is a fundamental model for studying gra...
research
∙
06/18/2021
Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle
Motivated by applications in crowdsourced entity resolution in database,...
research
∙
06/07/2021
Local Algorithms for Estimating Effective Resistance
Effective resistance is an important metric that measures the similarity...
research
∙
05/26/2021
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem
We contribute to the theoretical understanding of randomized search heur...
research
∙
05/18/2021
GSF-locality is not sufficient for proximity-oblivious testing
In Property Testing, proximity-oblivious testers (POTs) form a class of ...
research
∙
11/02/2020
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest
We give two fully dynamic algorithms that maintain a (1+ε)-approximation...
research
∙
08/13/2020
On Testability of First-Order Properties in Bounded-Degree Graphs
We study property testing of properties that are definable in first-orde...
research
∙
06/25/2020
Augmenting the Algebraic Connectivity of Graphs
For any undirected graph G=(V,E) and a set E_W of candidate edges with E...
research
∙
06/07/2020
Average Sensitivity of Spectral Clustering
Spectral clustering is one of the most popular clustering methods for fi...
research
∙
05/28/2020
More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization
Dynamic optimization problems have gained significant attention in evolu...
research
∙
05/04/2020
Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time
We present a simple sublinear-time algorithm for sampling an arbitrary s...
research
∙
07/10/2019
Constant-Time Dynamic (Δ+1)-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
With few exceptions (namely, algorithms for maximal matching, 2-approxim...
research
∙
05/05/2019
Testable Properties in General Graphs and Random Order Streaming
We present a novel framework closely linking the areas of property testi...
research
∙
04/22/2019
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
Due to the massive size of modern network data, local algorithms that ru...
research
∙
12/25/2018
Mixed-Order Spectral Clustering for Networks
Clustering is fundamental for gaining insights from complex networks, an...
research
∙
11/07/2018
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
One of the most fundamental questions in graph property testing is to ch...
research
∙
02/26/2018
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
We consider the problem of dynamically maintaining (approximate) all-pai...
research
∙
12/18/2017
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
We introduce a new algorithmic framework for designing dynamic graph alg...
research
∙
11/13/2017