Shahrzad Haddadan, Rutgers University

Abstract

In this talk, I will present a few results on a number of graph exploration problems in the following natural scenario: an algorithm starts exploring an undirected graph from some seed vertex; the algorithm, for an arbitrary vertex v that it is aware of, can ask an oracle to return the set of the neighbors of v. The goal of the algorithm is to either learn something (e.g., average degree, number of motifs, etc) about the graph, or to return some random function of the graph (e.g., a uniform-at-random vertex), while accessing/downloading as few vertices of the graph as possible. This model, known as the random walk model or the neighborhood query model has been introduced recently and captures real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely and sampling vertices independently is non-trivial in it.

I will first consider the problem of sampling a vertex uniformly at random and the problem of estimating the average of a bounded function on the vertices of the graph, and I will present lower bound results showing folklore algorithms are optimal. Then, I will discuss some implications of the lowerbound results on the solution of other problems e.g., counting triangles, cliques or near cliques. I will finish my talk with a few open problems about this model.

See: https://theory.cs.rutgers.edu/theory_seminar