Associate Professor
Laboratory of Artificial Intelligence and Learning Algorithms (LAILA)
Department of Computer Science, University of Milan
& Milan ELLIS Unit (https://www.ellismilan.eu/)
email: marco.bressan at unimi.it
interests: graph/randomized/learning algorithms
Cerco studenti interessati a svolgere tirocini, sia teorici che implementativi, idealmente su:
- teoria del machine learning
- grafi e machine learning
- algoritmi per l'analisi di grandi grafi
- conteggio e campionamento di sottografi
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
Jun 2025: A Theory of Generalized Boosting, Bocconi Theory Day, Bocconi University
Sep 2024: A Theory of Interpretable Approximations, Bocconi University
Jul 2024: Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees, ICML 2024
Jun 2024: Efficient and near-optimal algorithms for sampling connected subgraphs, Simons Institute for the Theory of Computing
Mar 2024: A Theory of Interpretable Approximations, University of Padova
Sep 2022: Cluster Recovery In R^m With Oracle Queries, ELLIS@Milan AI Workshop
Dec 2021: On Margin-Based Cluster Recovery with Oracle Queries, NeurIPS '21
Oct 2021: Google's Workshop on Scalable Algorithms for Semi-supervised and Unsupervised Learning Workshop (2 posters)
Sep 2021: Exact recovery of clusters in metric spaces: margins and convexities, ML research unit @ TU Wien
Aug 2021: Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries, COLT '21
Jun 2021: Efficient and near-optimal algorithms for sampling connected subgraphs, ACM STOC '21
Feb 2021: Efficient and near-optimal algorithms for sampling connected subgraphs, Google Zurich
Dec 2020: Efficient and near-optimal algorithms for sampling connected subgraphs, ALGADIMAR National Project Meeting
Dec 2020: Exact recovery of mangled clusters with same-cluster queries, NeurIPS 2020 (oral)
PC member of: COLT 2023, ACM KDD 2023 (excellent reviewer), WWW 2023, ACM WSDM 2023, ACM KDD 2022, COLT 2022 (outstanding reviewer), WWW 2022, COLT 2021, WWW 2021, ...
Regularly reviewing for: TKDD, TALG, JCSS, VLDBJ, SODA, ICALP, ICML, COLT, NeurIPS, WWW, ...
Programmazione 1, 2022/2023 and 2023/2024, BS in Computer Science
Fundamentals of Data Science and Laboratory (home page), 2019/2020, Master's Degree in Data Science
Algorithms, 2018/2019, Bachelor's Degree in Bioinformatics
Fundamentals of Data Science and Laboratory (home page), 2018/2019, Master's Degree in Data Science