Publications

M. B., J. Brinkmann, H. Dell, M. Roth, P. Wellnitz.
The Complexity of Counting Small Sub-Hypergraphs. SODA 2026 (to appear).
preprint: https://arxiv.org/abs/2506.14081

F. Agrimonti, M.B., T. d'Orsi.
On Finding Randomly Planted Cliques in Arbitrary Graphs. APPROX 2025.
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.11

M.B., N. Brukhim, N. Cesa-Bianchi, E. Esposito, Y. Mansour, S. Moran, M. Thiessen.
A Fine-grained Characterization of PAC Learnability.  COLT 2025.
https://proceedings.mlr.press/v291/bressan25b.html

M.B., N. Brukhim, N. Cesa-Bianchi, E. Esposito, Y. Mansour, S. Moran, M. Thiessen.
Of Dice and Games: A Theory of Generalized Boosting.  COLT 2025.
https://proceedings.mlr.press/v291/bressan25a.html

Y. Bourreau, M. B., T-H. Hubert Chan, Q. Kuang, M. Sozio.
Efficient Streaming Algorithms for Graphlet Sampling.  NeurIPS 2024.
https://openreview.net/forum?id=EC9Hfi9V3k

M. B., L. A. Goldberg, K. Meeks, M. Roth.
Counting Subgraphs in Somewhere Dense Graphs.  SICOMP 53(5). 2024.
https://epubs.siam.org/doi/10.1137/22M1535668

M. B. and M. Sozio.
Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees.  ICML 2024.
https://icml.cc/virtual/2024/poster/33567

M.B., E. Esposito, M. Thiessen.
Efficient Algorithms for Learning Monophonic Halfspaces in Graphs.  COLT 2024.
https://proceedings.mlr.press/v247/bressan24b.html

M.B., N. Cesa-Bianchi, E. Esposito, Y. Mansour, S. Moran, M. Thiessen.
A Theory of Interpretable Approximations.  COLT 2024.
https://proceedings.mlr.press/v247/bressan24a.html

M. B., N. Cesa-Bianchi, S. Lattanzi, A. Paudice.
Margin-Based Active Learning of Classifiers.  JMLR 25(127):1−45, 2024.
https://www.jmlr.org/papers/v25/22-1127.html

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

M.B.
Efficient and near-optimal algorithms for sampling small connected subgraphs.  ACM TALG 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: ...  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 TKDD. 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

(See my DBLP entry for more)