1) 19.03.2026
WHO: Dr. Talya Eden, Bar-Ilan University
WHEN: Thursday, March 19th 2026 at 12:00
WHERE: VIA ZOOM ONLY - https://biu-ac-il.zoom.us/j/86044603940
Title: Approximately counting and sampling Hamiltonian motifs in sublinear-time
Abstract: Counting small subgraphs, known as motifs, within large graphs is a fundamental challenge in graph analysis. In this talk, I will introduce a novel algorithm in the standard query model for approximately counting and almost uniformly sampling any Hamiltonian motif in sublinear time. Our approach highly simplifies prior approximate counting algorithms for edges, cliques, and stars in the standard model. This work marks a significant step toward narrowing the gap between results achievable in the standard model and the more powerful augmented query model.
Joint work with Reut Levi, Dana Ron and Ronitt Rubinfeld
