אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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