Publications

M. B. and M. Sozio.  Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees.
http://arxiv.org/abs/2302.03994

M. B., N. Cesa-Bianchi, S. Lattanzi, A. Paudice. Margin-Based Active Learning of Classifiers.
Journal of Machine Learning Research (in press).

M. B., L. A. Goldberg, K. Meeks, M. Roth.  Counting Subgraphs in Somewhere Dense Graphs.
SIAM Journal on Computing (in press).

M. B., E. Peserico, L. Pretto.  Sublinear Algorithms for Local Graph-Centrality Estimation.
SIAM Journal on Computing 52(4). 2023. https://epubs.siam.org/eprint/KUZJIQ5ZU34FTEHE6B7B/full

M.B.  Efficient and near-optimal algorithms for sampling small connected subgraphs
ACM Transactions on Algorithms 19(3). 2023.  https://dl.acm.org/doi/10.1145/3596495

M. B., M. Lanzinger, M. Roth.  The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree.
ACM STOC 2023.  https://dl.acm.org/doi/abs/10.1145/3564246.3585204

M. B., G. Damay, M. Sozio.  Fully-Dynamic Decision Trees.
AAAI 2023 (oral).  https://ojs.aaai.org/index.php/AAAI/article/view/25838

M. B., L. A. Goldberg, K. Meeks, M. Roth.  Counting Subgraphs in Somewhere Dense Graphs.
ITCS 2023. https://doi.org/10.4230/LIPIcs.ITCS.2023.27 

M. B., N. Cesa-Bianchi, S. Lattanzi, A. Paudice, M. Thiessen.  Active Learning of Classifiers with Label and Seed Queries
NeurIPS 2022. PDF

M. B., N. Cesa-Bianchi, S. Lattanzi, A. Paudice.  On Margin-Based Cluster Recovery with Oracle Queries
NeurIPS 2021. Full paper

M. B. and M. Roth.  Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
IEEE FOCS 2021. PDF (full version at http://arxiv.org/abs/2103.05588)

M. B., N. Cesa-Bianchi, S. Lattanzi, A. Paudice.  Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
COLT 2021. Full paper

M.B.  Efficient and near-optimal algorithms for sampling connected subgraphs
ACM STOC 2021. PDF (full version at https://arxiv.org/abs/2007.12102)

M. B., S. Leucci, A. Panconesi.  Faster motif counting via succinct color coding and adaptive sampling
ACM Trans. Knowl. Disc. Data. 2021.  https://doi.org/10.1145/3447397

M. B.  Faster subgraph counting in sparse graphs
Algorithmica (IPEC special issue). 2021.  https://doi.org/10.1007/s00453-021-00811-0

M. B., N. Cesa-Bianchi, S. Lattanzi, A. Paudice.  Exact Recovery of Mangled Clusters with Same-Cluster Queries
NeurIPS 2020 (oral, acceptance rate 1%).  Full paper

M. B., E. Peserico, L. Pretto.  On approximating the stationary distribution of time-reversible Markov chains
Theory Comput. Syst. 64 (STACS special issue). 2020.  PDF

M. B., N. Cesa-Bianchi, A. Paudice, F. Vitale.  Correlation Clustering with Adaptive Similarity Queries
NeurIPS 2019. PDF

M. Agostini, M. B., S. Haddadan.  Mixing time bounds for graphlet random walks
Inf. Process. Lett., Aug 2019. DOI

M. B.  Faster subgraph counting in sparse graphs
IPEC 2019. DOI

M. B., S. Leucci, A. Panconesi.  Motivo: fast motif counting via succinct color coding and adaptive sampling
VLDB 2019. PDF

M. B., E. Peserico, L. Pretto.  Sublinear algorithms for local graph centrality estimation
IEEE FOCS 2018.  PDF and full version on ArXiv

M. B., E. Peserico, L. Pretto.  Brief Announcement: On Approximating PageRank Locally with Sublinear Query Complexity
ACM SPAA 2018. PDF

M. B., F. Chierichetti, R. Kumar, S. Leucci, A. Panconesi.  Motif Counting Beyond Five Nodes
ACM Trans. Knowl. Disc. Data, 12 (4), July 2018.  PDF

M. B., E. Peserico, L. Pretto.  On Approximating the Stationary Distribution of Time-reversible Markov Chains
STACS 2018.  PDF

(See my DBLP entry for more)