##### Department of Mathematics,

University of California San Diego

****************************

### Math 196 - Student Colloquium

## Jacques Verstraete

#### UC San Diego

## Decentralized Search in Networks

##### Abstract:

It is known both scientifically and anecdotally that typical large-scale social networks exhibit short paths between pairs of nodes, hence the common phrase ``six degrees of separation''. In this talk, mathematical background for this phenomenon is given, together with a study of the algorithmic question of how to search such large-scale networks using only local information. In particular, one could imagine that each person in the network is allowed to pass a message to one of their acquaintances, until a particular target person in the network receives the message. Remarkably, for many networks with $n$ nodes, there is a simple algorithm which does this extremely efficiently -- a ``decentralized search'' algorithm which runs in time polylogarithmic in the number of nodes. The mathematics in this talk involves only elementary combinatorics and probability.

Host: Glenn Tesler

### October 30, 2020

### 3:00 PM

### Contact Glenn Tesler for Zoom link

****************************