Theory Seminar, Wednesday Feb 14: Talya Eden (BIU) - Algorithmic Techniques in Counting and Sampling Subgraphs in Sublinear-Time

[Talya Eden]

Hi all,
Next week we will meet as usual.

Time: 14.02.2024, 12:00

Location:  Building 503 room 226.

Best,

Arnold and Talya

Speaker: Talya Eden (BIU)

Title: Algorithmic techniques in counting and sampling subgraphs in sublinear-time

Abstract: 

In this talk I will review several results from the past few years on counting and sampling subgraphs in sublinear time. 

In particular, I will present an optimal algorithm for sampling edges in sublinear time, and give a short overview of how to extend it to sampling edges in bounded arboricity graphs, and then how to go from edges to $k$-cliques.
I will also discuss a few subroutines that are useful in various algorithms - sampling outgoing neighbors, sampling high-degree vertices and simulating edge samples.

[Arnold Filtser]

The seminar starts in 45 minutes!

--
You received this message because you are subscribed to the Google Groups "BIU Theory Seminar" group.
To unsubscribe from this group and stop receiving emails from it, send an email to biu-theory-semi...@cs.biu.ac.il.
To view this discussion on the web visit https://groups.google.com/a/cs.biu.ac.il/d/msgid/biu-theory-seminar/CAHYGKUzygxdT6se10tOZPH_0s%2B5iTfHbEhUNHdNtbSqxOdiT-g%40mail.gmail.com.
For more options, visit https://groups.google.com/a/cs.biu.ac.il/d/optout.