research
∙
02/08/2023
Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees
We give the first algorithm that maintains an approximate decision tree ...
share
research
∙
12/01/2022
Fully-Dynamic Decision Trees
We develop the first fully dynamic algorithm that maintains a decision t...
research
∙
11/03/2022
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
We study the fixed-parameter tractability of the following fundamental p...
research
∙
09/08/2022
Active Learning of Classifiers with Label and Seed Queries
We study exact active learning of binary and multiclass classifiers with...
research
∙
09/07/2022
Counting Subgraphs in Somewhere Dense Graphs
We study the problems of counting copies and induced copies of a small p...
research
∙
06/09/2021
On Margin-Based Cluster Recovery with Oracle Queries
We study an active cluster recovery problem where, given a set of n poin...
research
∙
03/09/2021
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
We study the problems of counting the homomorphisms, counting the copies...
research
∙
01/31/2021
Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
We investigate the problem of exact cluster recovery using oracle querie...
research
∙
09/04/2020
Faster motif counting via succinct color coding and adaptive sampling
We address the problem of computing the distribution of induced connecte...
research
∙
07/23/2020
Sampling connected subgraphs: nearly-optimal mixing time bounds, nearly-optimal ε-uniform sampling, and perfect uniform sampling
We study the connected subgraph sampling problem: given an integer k ≥ 3...
research
∙
06/08/2020
Exact Recovery of Mangled Clusters with Same-Cluster Queries
We study the problem of recovering distorted clusters in the semi-superv...
research
∙
06/04/2019
Motivo: fast motif counting via succinct color coding and adaptive sampling
The randomized technique of color coding is behind state-of-the-art algo...
research
∙
05/28/2019
Correlation Clustering with Adaptive Similarity Queries
We investigate learning algorithms that use similarity queries to approx...
research
∙
05/05/2018
On exploiting degeneracy to count subgraphs
Motivated by practical applications, we study the complexity of counting...
research
∙
05/05/2018
On degeneracy and the parameterized complexity of subgraph counting
We study the complexity of counting the (induced) occurrences of a k-nod...
research
∙
12/30/2017