18 citations · 58 across the 16 of their papers we have counts for
18 papers
Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees
Marco Bressan, Mauro Sozio
We give the first algorithm that maintains an approximate decision tree over an arbitrary sequence of insertions and deletions of labeled examples, with strong guarantees on the wo…
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…
Active Learning of Classifiers with Label and Seed Queries
Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi +2
We study exact active learning of binary and multiclass classifiers with margin. Given an -point set , we want to learn any unknown classifier on who…
Counting Subgraphs in Somewhere Dense Graphs
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks +1
We study the problems of counting copies and induced copies of a small pattern graph in a large host graph . Recent work fully classified the complexity of those problems ac…
On Margin-Based Cluster Recovery with Oracle Queries
Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi +1
We study an active cluster recovery problem where, given a set of points and an oracle answering queries like "are these two points in the same cluster?", the task is to recove…
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
Marco Bressan, Marc Roth
We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a -vertex graph in a -degenerate -vertex graph . Our ma…