Theory Seminar - "Sampling Edges and More"
Abstract: In this talk, we consider the problem of sampling an edge (almost) uniformly at random from a graph $G$ in sub-linear time. First, we describe a simple algorithm for this task that is optimal in the worst case. We then describe a generalization of the procedure that is more efficient when a non-trivial upper bound on $G$'s arboricity is known. We conclude by discussing recent developments and open questions. This talk is based on joint works with Talya Eden (MIT & BU) and Dana Ron (Tel Aviv University).
Bio:Will grew up in the Seattle area. He studied mathematics at Reed College, and completed his PhD in mathematics at UCLA. He spent two years as a postdoctoral fellow at Tel Aviv University, followed by two years as a postdoctoral researcher at the Max Planck Institute for Informatics in Saarbrucken, Germany. He is currently Assistant Professor of Computer Science at Amherst College. Before beginning his academic career, Will worked as a snowboard instructor, nuclear reactor operator, and fishmonger.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.