Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

CS LECTURE: Sublinear-time Graph Algorithms: Motif Counting and Uniform Sampling
event speaker icon
Talya Eden (MIT and Boston University)
event date icon
Sunday, 09.01.2022, 10:30
event location icon
Room 012 Taub Bld (Learning Center Auditorium)
In this talk I will survey recent developments in approximate subgraph-counting and subgraph-sampling in sublinear-time. Counting and sampling small subgraphs (aka motifs) are two of the most basic primitives in graph analysis, and have been studied extensively, both in theory and in practice. In my talk, I will present the sublinear-time computational model, where access to the input graph is given only through queries, and will explain some of the concepts that underlie my results. I will then explain how we can get improved bounds for a very natural graph family: the family of bounded arboricity graphs. Finally, I'll present a recent application, where again we take advantage of the unique structure of social networks in order to get improved bounds for a very basic and well-studied problem. Bio: Talya Eden is a postdoctoral fellow jointly affiliated with MIT and Boston University. She works on sublinear-time graph algorithms and randomized algorithms for huge data sets. Her work focuses on theoretical and applied graph parameter estimation in sublinear-time, as well as graph algorithms in other related areas, such as the streaming model, the massively parallel computation model, and learning-augmented algorithms. Talya completed her PhD at the School of Electrical Engineering at Tel Aviv University under the supervision of Prof. Dana Ron, and then continued on to a postdoctoral fellowship with the Foundations of Data Science Institute at MIT. Talya has won several awards for her work, including the EATCS Distinguished Dissertation Award in Theoretical Computer Science, a Rothschild Postdoctoral Fellowship, a Schmidt Postdoctoral Award, a Ben Gurion University postdoctoral fellowship, a Weinstein Graduate Studies Prize, and the Azrieli Fellows Scholarship. Website: