Portrait of me

Marco Bressan

Assistant Professor (RTD-B)
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

Latest 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., 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 (to appear). Preprint at https://arxiv.org/abs/2209.03996

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)

For Students

If you are interested in a bachelor's thesis or master's thesis, just email me. I have several topics on which you can work (especially graph algorithms, but also machine learning).

Se siete interessati in una tesi triennale o una tesi magistrale, mandatemi una mail. Ho svariati argomenti sui quali lavorare (specialmente algoritmi su grafi, ma anche machine learning).

Recent talks

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)

Recent Professional Service

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, ...

Teaching

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